Check duplicate in rows and columns 2D Array

Question

how would I go about checking a duplicate for columns and rows and return true or false depending if there's duplicates. For example

1 2 3

3 1 2

2 3 1

Would return true because no duplicates, but..

1 2 2

3 2 3

2 1 1

would return false because there is a duplicate in column 2 {2, 2, 1}.

How would I go about checking for if there are in duplicates in the rows and then checking if there are duplicates in the columns?

So far I have only the following:

public static boolean hasDuplicates(int [][] inArray)
{
   for (int row = 0; row < inArray.length; row++)
   {
      int rowCheck = inArray[row][inArray.length];
      for (int col = 0; col < inArray[row].length; col++)
      {

      }
   }
   return false;
}

So I need to take in an array and check if there are any duplicates among the columns or rows. Any pointers? Thank you!

NOTE: This cannot be done with outside methods

Solution 1

Go through each value in the row. For every value, check and see if any of the values after that value are the same. If the value is the same, return true (you've found a duplicate). If none of the values are the same, increment your index and do the same for the next row. Every row will take at most n(n+1)/2 comparisions which isn't wonderful. So if n is the number of columns and m in the number of rows, this will run, worst case m(n(n+1)/2) times.

Here is an example of how it would work for the rows:

/**
 * Return flag indicating if there are duplicates in the rows of the 2D array
 * 
 * @return true if a row has duplicates, else false
 */
public boolean hasDuplicatesInRows(int[][] inArray)
{
    for (int row = 0; row < inArray.length; row++)
    {
        for (int col = 0; col < inArray[row].length; col++)
        {
            int num = inArray[row][col];
            for (int otherCol = col + 1; otherCol < inArray.length; otherCol++)
            {
                if (num == inArray[row][otherCol])
                {
                    return true;
                }
            }
        }
    }

    return false;
}

That would be pretty easy to extend to do columns as well. I will leave that for you to do though.

If you used an efficient sorting method and sorted all the rows, you could just go down the line and see if any value was equal to the value after it. If it is, return true, else return false. This would be more efficient if you had a large data set.

Solution 2

A more compact way of achieving this task is to add all the values to a Set and then compare the number of unique elements in the Set to the original row size using guava.

public static boolean hasDuplicates(int [][] inArray) {
    for (int row = 0; row < inArray.length; row++) {
        int curRow = inArray[row];
        Set set = Sets.newHashSet(Arrays.asList(curRow));
        if (set.size() < curRow.length) {
            return true;
        }
    }
    return false;
}

Solution 3

for rows, try following this sort of procedure:

boolean dup = false;
for (int k = 0; k < inArray[0].length){ //loop through columns
  for (i = 0; i < inArray.length-1; i++) {
    for (int j = i; j < inArray.length; j++){
      if (inArray[k][i] == inArray[k][j]){
        dup = true;
        break;
      }
    }
  }
}

so, you're starting at the first element, then scanning from element 2 to n (ie number of columns). If a match is found, then you're setting the boolean to true. If no match, then i is incremented and the inner for loop is scanning from element 3 to n.

Follow a similar procedure for the columns, and you're done!

Solution 4

Let's say you create a method that operates on a single-dimensional array. You break the problem down into extracting strips of numbers from your 2d array into a 1d array. It's signature might look like boolean containsDupes(int[] strip) { ... }.

There are a couple of approaches in that method that would make it easier to solve. One would be to sort that array so the dupes are next to each other. Another would be to populate a HashSet with each value and compare the size of the Set with the length of your array.

View more solutions