Algorithm to verify if a two-dimensional array has two equals rows

Question

Define a method in which, given a two-dimensional array, evaluates if it has at least two identical rows

I've tried to come up with an algorithm to do it but I didn't go very far. This is what I got:

public static boolean righeUguali(int[][] a){
    boolean rUguali=false;

    for(int i=0; i<a.length; i++)
        for(int j=0; i<a[i].length; j++)
            if(Arrays.equals(a[i],a[j]))
                rUguali = true;
    return rUguali;

could you help me fix this code?

What you want to do with that algorithm, what is your problem with that code? — Youcef LAIDANI, Jun 13 '16 at 13:28
it doesn't work. there is obviously something wrong with it but I cannot figure out what it is. It should return true if 2 rows are identical — Daniele, Jun 13 '16 at 13:29
Possible duplicate of [Java Array, Finding Duplicates](http://stackoverflow.com/questions/3951547/java-array-finding-duplicates) — 4castle, Jun 13 '16 at 13:31
Have you tried a debugger or some debug-output to find the problem? — MrSmith42, Jun 13 '16 at 13:38
You'd also need to change `j=0` to `j=i+1`; otherwise you'll check arrays against themselves. — Andy Turner, Jun 13 '16 at 13:41

score 4 · Answer 1 · answered Jun 13 '16 at 13:45

4

You need to ensure that you are not comparing the row with itself. You ensure that by starting j with i+1
Both loops need to iterate over the rows
The fist of the two rows cannot be the last one, otherwise there would be no second row left to compare it to.
optimization: you can terminate as soon as you found two equal rows

Here the modified code:

public static boolean righeUguali(int[][] a){
    for(int i=0; i<a.length-1; i++)
        for(int j=i+1; i<a.length; j++)
            if(Arrays.equals(a[i],a[j]))
                return true;
    return false;
}

answered Jun 13 '16 at 13:45

MrSmith42

9,961
6
38
49

Thank you especially for the optimization – Daniele Jun 13 '16 at 14:31
@Daniele: It is still **O(n²)*.*: If speed is an issue: You can get **O(n)** by using a HashSet. – MrSmith42 Jun 13 '16 at 15:12
It's not a problem for a small method like this I think. But still I like to discover new ways to improve my code – Daniele Jun 13 '16 at 19:19

fill͡pant͡ · Accepted Answer · 2016-06-13T14:22:49.040

2

Here is how i would do it:

int[][] array = { { 1, 2, 3, 4, 5, 6 },
            { 7, 6, 8, 3 }, 
            { 1, 2, 3, 4 },
            { 1, 2, 3, 9, 5, 6, 32, 3125423 },
            { 8, 3 }, 
            { 1, 2, 3, 4, 5, 6 } };//same as first row
    external: for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (Arrays.equals(array[i], array[j])) {
                System.out.println("Row: " + i + " is the same as row: " + j+" (warning! 0 oriented!)" );
                break external;
            }
        }
    }

As you see, array[] is quite random, but the first row (row 0) is the same as the last (row 5) so what i do then, is to loop through the array once and in every pass loop through the remaining rows of the array. Then i compare the arrays to chech if they are the same. As you see the code prints out a message and then terminates (stoping the external loop)

This is based on a simple sort algorythm.

EDIT #1 As @4castle pointed out in the comments, in the context of a method the break statement is not required and can be replaced by return.

edited Jun 13 '16 at 14:22

answered Jun 13 '16 at 13:41

fill͡pant͡

1,147
2
12
24

1

Since this is in a method, you can use the `return` to terminate the loops instead of breaking a named loop. – 4castle Jun 13 '16 at 13:56
@4castle Indeed, but i didn't really aim for a method because actually this piece of code is extracted from a project of mine. Anyways ill m ention that in my post :) **Thank you!** – fill͡pant͡ Jun 13 '16 at 14:16
Thank you very much! it fixed my problem – Daniele Jun 13 '16 at 14:25
@Daniele I'm glad i could help! :- ) – fill͡pant͡ Jun 13 '16 at 14:56

score 2 · Answer 3 · edited May 23 '17 at 12:14

By applying the simplest answer from the near-duplicate question:

public static boolean righeUguali(int[][] a) {
    for(int i = 0; i < a.length; i++)
        for(int j = i + 1; j < a.length; j++)
            if(Arrays.equals(a[i], a[j]))
                return true;
    return false;
}

Your algorithm is breaking because j is seemingly there to iterate over the nested array. That isn't needed because Arrays.equals will iterate over the nested array. Instead, use it as the second iterator for finding if any of the other elements match the current element specified by i.

If you want better performance, there are faster solutions on the duplicate question.

score 1 · Answer 4 · answered Jun 13 '16 at 14:53

No one has yet mentioned that a much faster way is to sort the top-level array, and then look for two adjacent rows that are identical. If the array is m*n, this will take O(mn log n) time, as opposed to all existing solutions which take O(mn^2) time.

Of course, if you can't reorder the rows then you'll need to make a copy of the array first -- but unless your array takes up > 50% of available RAM, creating the copy and then sorting its rows will still be much faster than the existing solutions.

You're welcome :) Sorting is one of those things in CS that turns out to be useful in unexpected places! — j_random_hacker, Jun 14 '16 at 09:12

Algorithm to verify if a two-dimensional array has two equals rows

4 Answers4