Determine whether rows in 2D array are unique

Question

I'm trying to create an algorithm which determines whether or not all of the rows in a 2D array of integers are unique (i.e. disjoint). Currently, I have a brute force algorithm which checks each value in each row to each value in the other rows, but I'd like to speed this up. Is there some kind of divide and conquer method to handle this? I have found some semi-solutions for this in single arrays and lists, but not in 2d arrays.

Answer 1

If you want to check whether there are two rows that contain the same number, you can put all the numbers along with numbers of rows that they belong to into one long list. Then sort this list which will make all the identical numbers stand next to each other. Than you can easily determine for each cluster of identical numbers whether they originally belonged to the same row or not.

If your table is n × m, the algorithm will run in O(nm × (log(n) + log(m))).

Answer 2

To test whether any two rows are disjoint**, make two sets (like java sets that reject duplicates and do so in almost O(1) time), one for each row and count the elements of each.

The two rows are disjoint if:

count(rowASet) + count(rowBSet) == count( union(rowASet, rowBSet) )

This suggests an algorithm for a 2D array where a rows are successively added (as sets) to a running total set. The count of the total set is measured before and after the addition of each row's set. If that count increases by the size of the row set just added, then the row just added is disjoint from those added so far.

**See the conversation with @CandiedOrange. I'm taking "disjoint row" to mean a row that contains no element found in any other row, but might itself contain repeated elements internally.

Answer 3

If you are allowed to use java collections consider using java's HashSet. It was designed for things like this:

areDisjoint() inspired by http://www.geeksforgeeks.org/check-two-given-sets-disjoint/

import java.util.*;

public static void main (String[] args)
{        

    int[][] twoD = {{3,3,3},{4,4,4},{5,5,5}};
    if ( disjointRows(twoD) )
    {
        System.out.println("Mutually disjoint rows");
    }
    else
    {
        System.out.println("Some element duplicated in other row");
    }
}

public static boolean disjointRows(int[][] twoD)
{

    // -- Copy 2D array into data structure -- //

    ArrayList<HashSet<Integer>> rows = new ArrayList<HashSet<Integer>>();

    for (int[] row : twoD)
    {            
        HashSet<Integer> hs = new HashSet<Integer>();
        for (int elem : row)
        {
            hs.add(elem);                
        }
        rows.add( hs );
    }

    // Above is O = r*c time just as it would be to copy the 2D array. 
    // or you can express it as O(n^2)


    // -- Mutual disjoint rows test -- //

    // Compare every combination of rows
    for (int y=1; y< rows.size(); y++)
    {
        for (int x=0; x<y; x++)
        {
          //TODO remove debugging code                
            System.out.print(areDisjoint( rows.get(x), rows.get(y) ) );
            System.out.print("=");
            System.out.print("(" + x + "," + y + ")  ");

            if (! areDisjoint( rows.get(x), rows.get(y) )  )
            {
                return false;
            }
        }
        System.out.println("");
    }
    return true;
    //Above is O = r(r-1)/2 * c 
    //or you can express it as O(n^3)
}

static boolean areDisjoint(Set<Integer> set1, Set<Integer> set2)
{
    //set1 must not contain anything in set2 
    for (int i : set2)
    {
        if ( set1.contains(i) )
            return false;
    }
    return true;
    // Above is c or O(n) because contains lookup is O(1)
}

Output:

// true=(0,1)
// true=(0,2) true=(1,2)
// Mutually disjoint rows

I can't tell if this is better than your "brute force" solution since you didn't post it.

I can tell from a big O notation perspective this is neck and neck with japreiss's solution. We're both at O(n^3). This solution uses more memory because it copies the 2D array rather than mutate it. When performance is equal I strongly urge you to pick your algorithm based on readability. I admit mine is longer. I took the time to comment it.

See also: Is a Java hashmap really O(1)?

//         If each row is to be disjoint from all other rows then
//         then testing them all against each other would produce
//         this truth table.  
//        
//                0    1    2   
//              |----|----|----|
//            0 | F  | T  | T  |
//              |----|----|----|
//            1 | T  | F  | T  |
//              |----|----|----|
//            2 | T  | T  | F  |
//              |----|----|----|
//        
//         Testing a row against it self can be ignored as can        
//         tests that simply transpose the input rows. Leaving us with
//        
//                0    1    2   
//              |
//            0 | 
//              |----|
//            1 | T  |
//              |----|----|
//            2 | T  | T  |
//              |----|----|
//        
//         So long as that's true, the rows are mutually disjoint

Answer 4

EDIT: my answer was slow and stupid. Or to put it more kindly, it was doing unnecessary work because it computed which two rows intersect instead of whether or not any two rows intersect.

After I posted I thought of 2 faster algorithms but they turned out to be Danylo Mysak's answer and the "running total set" danh hinted at.

I would still like to benchmark these different approaches.