Unique value finder

For our first assignment in our algorithm class we are suppose to solve several different questions using information from a 2D array. We are also suppose to optimize our code to get more marks on our assignment. We also are only allowed to use 1D and 2D arrays as the only data structure.

The problem was find the unique values in a 2D array (int data[][]) of 1000x250 values. The range of that is from 2000000 to 2200000. My idea was to make a 1D array (with 200000 indexes) and look at the number in the 2D array and see it matches anything prior to it in the 1D array, and if not, add it. However, with all the other questions, it takes a few seconds before it will actually finish.

int[] uniqueValues = new int[200000];
    boolean isUnique = true;
    int uniqueCounter = 0;

     for (int i = 0; i < data.length; i++) {

         for (int j = 0; j < data[i].length; j++) {

            for (int x = 0; x < uniqueCounter; x++) {

                if (data[i][j] != uniqueValues[x]) {
                    isUnique = true;
                } else {
                    isUnique = false;
                    break;
                }

            }

            if (isUnique) {
                uniqueValues[uniqueCounter] = data[i][j];
                uniqueCounter++;
            }

        }
}

Linear time solution

Given that your values are restricted to the range [2000000..2200000], you can do the following:

• Iterate through your matrix and keep a count of each of the numbers that you find in the matrix. You will need an array of size 200001 to keep these counts.

• Iterate through your count array. Whatever numbers have a count of 1 are unique.

Here is some sample code:

final int MIN_RANGE = 2000000;
    final int MAX_RANGE = 2200000;
    int[] count = new int[MAX_RANGE-MIN_RANGE+1];

    // Determine the count for each number.
    for (int i = 0; i < data.length; i++) {
        for (int j = 0; j < data[i].length; j++) {
            count[data[i][j] - MIN_RANGE]++;
        }
    }

    // Find out how many unique numbers there are.
    int uniqueCount = 0;
    for (int i = 0; i < MAX_RANGE-MIN_RANGE+1; i++) {
        if (count[i] == 1) {
            uniqueCount++;
        }
    }

    // Create an array of all the unique numbers.
    int [] uniqueValues = new int[uniqueCount];
    for (int i = 0, j = 0; i < MAX_RANGE-MIN_RANGE+1; i++) {
        if (count[i] == 1) {
            uniqueValues[j++] = i + MIN_RANGE;
        }
    }

This will reduce the worst case time from \$O(n^2)\$ to \$O(n)\$, where \$n\$ is the number of elements in the matrix (this depends on the range of values being smaller than the size of the matrix as in the question). If the range of values was not restricted, you could still do better by sorting the array of values and then scanning the sorted array for unique elements. That would take \$O(n \log n)\$ time. If you could use data structures other than arrays, you could use a HashMap instead of a count array and get \$O(n)\$ time again.

StackExchange Code Review Q#105208, answer score: 10