Count the number of unique elements in a sorted array

Question

Write a method named numUnique that accepts a sorted array of integers as a parameter and that returns the number of unique values in the array. The array is guaranteed to be in sorted order, which means that duplicates will be grouped together.

I'm mainly concerned with following proper conventions and maximizing readability; both of which I feel I know little about. In the last question I posted, I learned a bit about structuring if-statements. How can I think about these statements so that it's easier for me to write them, as well as easier for others to read them? Is there a sort of PEMDAS of programming logic that would help me understand writing conditional code with precedence? Any feedback is appreciated!

public static int numUnique(int[] array){
    if(array.length > 0){
        int countUnique = 1;
        for(int i = 0; i < array.length - 1; i++){
            if(array[i] != array[i+1]){
                countUnique++;
            }
        }
        return countUnique;
    } else {
        return 0;
    }
}

Answer 1

Just a few minor suggestions:

• If you invert the condition on the length, then you can reduce the level of nesting, which is slightly easier to read
• An array will never have a negative length. It's pure paranoia to check for array.length <= 0, I suggest to replace with array.length == 0
• The spacing is not perfect. Use an IDE to reformat the code
• This maybe a matter of taste, but I would rename countUnique to simply count, and the method from numUnique to countUnique

Putting it together:

public static int countUnique(int[] array) {
    if (array.length == 0) {
        return 0;
    }
    int count = 1;
    for (int i = 0; i < array.length - 1; i++) {
        if (array[i] != array[i + 1]) {
            count++;
        }
    }
    return count;
}

Answer 2

We could do a little bit better. It depends on what array ends up looking like, but what if we had like 100 0s and then 500 1s. Do we really need to compare each one individually?

No, we don't. We can binary search the next element.

private static int upper_bound(int[] array, int lo, int hi, int val) {
    int count = hi - lo;
    while (count > 0) {
        int step = count/2;
        int cur = lo + step;

        if (val >= array[cur]) {
            lo = cur + 1;
            count -= step + 1;
        }
        else {
            count = step;
        }
    }
    return lo;
}

And then use that to increment:

public static int countUnique(int[] array) {
    int count = 0;
    int idx = 0;
    while (idx < array.length) {
        ++count;

        // exponential search to find the next elem
        int bound = 1;
        while (idx+bound < array.length && array[idx+bound] == array[idx]) {
            bound *= 2;
        }

        idx = upper_bound(array,
            idx+bound/2,
            Math.min(idx+bound, array.length),
            array[idx]
        );
    }

    return count;
}

Answer 3

Expanding @janos's answer a bit:

• Instead of:

  for (int i = 0; i < array.length - 1; i++) {
      if (array[i] != array[i + 1]) {
  

  I would usually do:

  for (int i = 1; i < array.length; i++) {
      if (array[i] != array[i - 1]) {
          // ...
  

  Because, in my opinion, is easier to understand. I like this because I don't like the - sign in the condition. Of course, this is a matter of preference.

• Since you use array.length twice, I would make it a variable, but, your choice.

• I don't really like edge-case checks. I prefer the algorithm to be able to handle all cases, but in this case, it looks impossible. You can do:

  public static int countUnique(int[] array) {
      int length = array.length;
      int count = 1;
      for (int i = 1; i < length; i++) {
          if (array[i] != array[i - 1]) {
              count++;
          }
      }
      return length == 0 ? 0 : count;
  }
  

  But the ternary is like edge-case handling anyways. I don't think that's a good solution.

Result:

public static int countUnique(int[] array) {
    int length = array.length;
    if (length == 0) {
        return 0;
    }
    int count = 1;
    for (int i = 1; i < length; i++) {
        if (array[i] != array[i - 1]) {
            count++;
        }
    }
    return count;
}

Answer 4

Building upon @Barry's answer, Java already has Arrays.binarySearch(int[], int, int, int) that can perform the binary search without having to write additional code ourselves. :)

Using a very similar approach of modeling the next index \$m\$ as where the next larger value (\$V\$) of the current value (\$arr[n]\$) should be inserted, we have the following BiFunction<int[], Integer, Integer> implementation:

private static final BiFunction<int[], Integer, Integer> STEPPER = (sorted, i) -> {
        int r = Arrays.binarySearch(sorted, i, sorted.length, sorted[i] + 1);
        return r < 0 ? Math.abs(r + 1) : r;
    };

We need to handle for r < 0 as \$V\$ may not exist in the array, in which case Arrays.binarySearch() will return (-(insertion point) - 1). For pre-Java 8, this can easily be converted into a method as well.

The full method can then be:

private static int countUnique(int[] sortedArray) {
    if (sortedArray.length == 0) {
        return 0;
    }
    int counter = 1;
    for (int i = STEPPER.apply(sortedArray, 0); i < sortedArray.length;
                i = STEPPER.apply(sortedArray, i)) {
        counter++;
    }
    return counter;
}

After taking care of handling an empty array, we initialize counter as 1 (for the first element) and i to be the index of the next larger value than the first element. After each loop, i is then assigned the index of the next larger value than the current iteration's element.

Visualizing the steps taken can be done with a slight modification to STEPPER:

private static final BiFunction<int[], Integer, Integer> STEPPER = (sorted, i) -> {
        int r = Arrays.binarySearch(sorted, i, sorted.length, sorted[i] + 1);
        r = r < 0 ? Math.abs(r + 1) : r;
        System.out.printf("DEBUG: current (index = %d, value = %d); "
                            + "next (index = %d, value = %s)%n",
                            i, sorted[i], r, 
                            r >= sorted.length ? "END" : sorted[r]);
        return r;
    };

Given this example:

countUnique(new int[]{0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5});

// Output
DEBUG: current (index = 0, value = 0); next (index = 4, value = 1)
DEBUG: current (index = 4, value = 1); next (index = 7, value = 2)
DEBUG: current (index = 7, value = 2); next (index = 11, value = 4)
DEBUG: current (index = 11, value = 4); next (index = 14, value = 5)
DEBUG: current (index = 14, value = 5); next (index = 19, value = END)
Input(19): [0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 5, 5, 5, 5]

The answer is the number of DEBUG lines printed, i.e. 5. It works by jumping across any indices of the numbers 0 -> 1 -> 2 -> 4 -> 5. The any index part is a known effect from the method's Javadoc:

If the range contains multiple elements with the specified value, there is no guarantee which one will be found.

This still suffices for our usage here as we only need to hit any of the next larger number. Also, since 3 is not present in the list, 4 is returned after 2, and this is where the check for r < 0 is required to convert the result of Arrays.binarySearch() to a positive, usable index.

Answer 5

Solution 1

Maybe for readability a recursive function is a proper solution in this case. But think about it carefully because it will strain the stack.

public static int getUniqueValueCount(int[] array) {
    if (array.length == 0) {
        return 0;
    } else if (array.length == 1) {
        return 1;
    } else {
        return getUniqueValueCount(Arrays.copyOfRange(array, 1, array.length)) 
                + ((array[0] == array[1]) ? 0 : 1);
    }
}

Pros

• getUniqueValueCount instead of numUnique --> more expressive name
• no for-int-i iteration --> less control structures
• no state involved, nearly functional
• positive formulation of main condition

Cons

• strains the stack
• additional array operations O(n^2)

Solution 2

The following solution is a summary of this discussion with some modifications to improve readability. It uses the binary search approach for efficiency and speed. Personally I am not that convinced of it because there are some specifics about Arrays.binarySearch(..) in the case of application and interpretation of the return value.

The return value can hold (as far as I understand) up to two things. In the normal case (key was found) the index of the (any?) key is returned. In the case when the binary search returns a negative value it is considered as "not found". Furthermore the value can be multiplied by (-1) to receive an insertion index. Finally you have to decrement the insertion index by 1.

   private static int getUniqueValueCount(int[] sorted) {
          int count = 0;
          for (int curentIndx = 0; (curentIndx = nextDeviationIndex(sorted, curentIndx)) != -1;) {
                 count++;
          }
          return count;
   }

   private static int nextDeviationIndex(int[] sorted, int currentIndex) {
          if (sorted.length == 1 && currentIndex == 0) {
                 return 1;
          } else if (currentIndex < sorted.length) {
                 return binarySearchNextDeviationIndex(sorted, currentIndex, sorted[currentIndex] + 1);
          } else {
                 return -1;
          }
   }

   private static int binarySearchNextDeviationIndex(int[] sorted, int startIndex, int key) {
          int searchResult = Arrays.binarySearch(sorted, startIndex, sorted.length, key);
          // this is very hard to get ...
          return searchResult < 0 ? -searchResult - 1 : searchResult;
   }

Although the solution inflates to three methods nobody can avoid the responsibilites involved to produce the result:

1. Counting while iterating over the interesting elements until there are no left
2. Decide how to find the next interesting element and provide the information if there is no element left
3. Provide an efficient search for the case of mass data

Solution 3 (OO)

This is an solution that shows how the responsibilities are cut in the OO. I guess this is the most verbose one for the given problem.

public static class DeviationIterator implements Iterator<Integer> {

    private int[] sorted;

    private int nextIndex;

    public DeviationIterator(int[] sorted) {
        super();
        this.sorted = sorted;
        this.nextIndex = calculateNextIndex();
    }

    @Override
    public boolean hasNext() {
        return nextIndex != -1;
    }

    @Override
    public Integer next() {
        if (nextIndex != -1) {
            int currentIndex = nextIndex;
            nextIndex = calculateNextIndex();
            return currentIndex;
        } else {
            throw new NoSuchElementException();
        }
    }

    private int calculateNextIndex() {
        if (sorted.length == 1 && nextIndex == 0) {
            return 1;
        } else if (nextIndex < sorted.length) {
            return binarySearchNextDeviationIndex(sorted, nextIndex,
                    sorted[nextIndex] + 1);
        } else {
            return -1;
        }
    }

}

private static int getUniqueValueCount(int[] sorted) {
    int count = 0;
    DeviationIterator deviationIterator = new DeviationIterator(sorted);
    while(deviationIterator.hasNext()) {
        deviationIterator.next();
        count++;
    }
    return count;
}

1. The iterator encapsulates the search algorithm
2. the getUniqueValueCount uses the iterator to count

The most interesting part is you can clearly see, where the responsibilities are located. Using the iterator pattern identifies the fragment -1 as the EOF for the iterator. The user of the iterator via contract has to ask for if another element is available, so the "Solution 2". But there -1 is not translated into false so the the caller has to interpret it by himself.