Finding duplicate INT in 2D array

Question

I'm stuck on this method.

public class Duplicate{


   public static boolean extra(int [][] grid)
   {
       for(int i = 0; i < grid.length; i++)
           for(int j = 0; j < grid[i].length-1; j++)
              if(grid[i][j] == grid[i][j+1])
              {
                  System.out.println(grid[i][j]);
                  return true;
              }
    return false;
   }

   public static void main(String[] args){

      int [][] grades = {{3,5,8,7},
                        {2,1,11,4},
                       {13,20,10,6},
                        {7,0,12,15}
                       };

       System.out.print(extra(grades));   
   }
 }

I want to find if there are any duplicated ints in the array. return true if there is and the int that is duplicated. My method keeps coming out FALSE. what am I doing wrong? Any help would be appreciated. Please and thank you.

You're only comparing one element of the array to the next, not comparing all of them. Have you learned about sets? If you put the contents of each cell in the a Set (docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E)) using add, you can check the return type. If it's false, you've got yourself a dupe! — LazyCubicleMonkey
– LazyCubicleMonkey, Commented Oct 10, 2013 at 2:33

arshajii · Accepted Answer · 2013-10-10 02:37:57Z

2

All your method is doing is checking if two consecutive elements are equal, which does not tell you anything about duplicates that are not adjacent. One way to do this would be to have a Map<Integer, Integer> that maps the values to their frequencies:

Map<Integer, Integer> map = new HashMap<>();

for (int[] row : grid) {
    for (int a : row) {
        map.put(a, map.containsKey(a) ? map.get(a) + 1 : 1);
    }
}

You can then loop over the entries of this map to find the elements with a frequency greater than or equal to 2.

edited Oct 10, 2013 at 2:37

answered Oct 10, 2013 at 2:31

arshajii

130k26 gold badges246 silver badges293 bronze badges

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

3 Comments

Java Devil Over a year ago

Shouldn't it be map.put(a, map.containsKey(a) ? map.get(a) + 1 : 1)

Marcella Ruiz Over a year ago

Is it possible to do the method with only for loops?

arshajii Over a year ago

@MarcellaRuiz Yes, you can implement a naive algorithm that checks each element against all others.

davecom · Accepted Answer · 2013-10-10 02:38:47Z

2

To rewrite your method so it works:

ArrayList<Integer> comeBefore = new ArrayList<Integer>();
for(int i = 0; i < grid.length; i++) {
    for(int j = 0; j < grid[i].length; j++) {
        if(comeBefore.contains(grid[i][j])) {
            System.out.println(grid[i][j]);
            return true;
        }
        comeBefore.add(grid[i][j]);
    }
}
return false;

I don't have time to think about it right now... but maybe a set or such would be a more efficient data structure to use for this. Also this code may not be right... but it's the gist of it; it's untested.

answered Oct 10, 2013 at 2:38

davecom

1,49812 silver badges31 bronze badges

Comments

Liu guanghua · Accepted Answer · 2013-10-10 02:41:09Z

1

private static boolean extra(int[][] data) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < data.length; i++) {
        for (int j = 0; j < data[i].length; j++) {
            if (set.contains(data[i][j])) {
                return true;
            } else {
                set.add(data[i][j]);
            }
        }
    }
    return false;
}

answered Oct 10, 2013 at 2:41

Liu guanghua

9911 gold badge9 silver badges18 bronze badges

1 Comment

arshajii Over a year ago

Although he wants to know the int that was a duplicate.

Java Devil · Accepted Answer · 2013-10-10 02:48:57Z

You are only comparing adjacent numbers in your loop with this line if(grid[i][j] == grid[i][j+1])

Like arshajii mentioned using a Map will is one way to do this. If you want to keep the co-ordinates of each duplicate then you could extend arshajii's answer to have a Map of Lists like so.

Map<Integer, List<Point>> map = new HashMap<>();

for(int i = 0; i < grid.length; i++)
{
    for(int j = 0; j < grid[i].length; j++)
    {
        int val = grid[i][j];
        if(map.containskey(val))
             map.put(val, map.get(val).add(new Point(i,j));
        else
        {
             List<Point> li = new ArrayList<>();
             li.add(new Point(i,j));
             map.put(val, li);
        }
    }
}

Then to get duplicates you find any key that has a size > 1 and you can get the co-ordinates

for(Integer key : map.ketSet())
{
     List<Point> li = map.get(key);
     if(li.size() > 1)
     {
          System.out.println("The value " + key +" was duplicated at the indices: ");
          for(Point p : li)
             System.out.println(p.x + ", " + p.y);
     }
}

But this is probably over the top!

Collectives™ on Stack Overflow

Finding duplicate INT in 2D array

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related