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

how is 3-2-3 not a "duplicate" in your first example? It's a little unclear what you're asking. — Brian Roach
– Brian Roach, Commented Feb 21, 2014 at 0:00
@BrianRoach my apologies! The third row should be 2-3-1, edited! — user3335070
– user3335070, Commented Feb 21, 2014 at 0:06
You may find your answer in this (exact same) question: stackoverflow.com/questions/6122315/… — Tim
– Tim, Commented Feb 21, 2014 at 0:33

spike · Accepted Answer · 2014-02-21 00:39:28Z

3

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;
}

edited Feb 21, 2014 at 0:39

answered Feb 21, 2014 at 0:33

spike

4421 gold badge7 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3335070 Over a year ago

this is for a program where I'm not allowed to use sets or lists. Sorry, I should have mentioned that above.

mdewitt · Accepted Answer · 2014-02-21 01:20:04Z

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.

edited Feb 21, 2014 at 1:20

answered Feb 21, 2014 at 0:28

mdewitt

2,55420 silver badges23 bronze badges

6 Comments

user3335070 Over a year ago

Sorry, I should have mentioned above that I can't use any outside methods. Thanks for your help though, wish I could go this route

user3335070 Over a year ago

done. Do you have any pointers for doing this without. I understand the concept I just don't know how to achieve it

mdewitt Over a year ago

@user3335070 I fixed my answer to not use Collections. It's almost the same as before, but it does a check for each value in the row against the other values. I'm not convinced this is the most efficient, but it does work and it's simple.

user3335070 Over a year ago

Thank you so much, I can't express how grateful I am.. I've been working on this since 11am and I've been in such a block. Thank you. To get columns would I then switch them around so the first for loop would be for (int col = 0; col < inArray[0].length; col++) then the row on the inside? Then substitute row for the otherCol?

user3335070 Over a year ago

Aweomse, thanks so much. You definitely saved me from pulling an all nighter!

|

phatfingers · Accepted Answer · 2014-02-21 00:33:02Z

1

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.

answered Feb 21, 2014 at 0:33

phatfingers

10.3k3 gold badges34 silver badges47 bronze badges

Comments

h_k · Accepted Answer · 2014-02-21 00:47:53Z

1

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!

edited Feb 21, 2014 at 0:47

answered Feb 21, 2014 at 0:03

h_k

1,7241 gold badge27 silver badges52 bronze badges

2 Comments

user3335070 Over a year ago

so would for (i = 0; i < n-1; i++) be for (i = 0; i < inArray.length-1; i++) and then the next be for(int j = i; j < inArray[i].length; j++)? Thank you for your help @h_k

h_k Over a year ago

Yes. I had "n" in there originally because I started making my answer more generalized. I'll throw that into my answer.

Collectives™ on Stack Overflow

Check duplicate in rows and columns 2D Array

4 Answers 4

1 Comment

6 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

6 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related