Counting Unique Values in Sorted Arrays

The problem

Count the number of unique values in a sorted array efficiently. This is a fundamental problem that demonstrates important algorithmic techniques.

Example:

countUniqueValues([1,1,2,3,3,4,5,5,5,6]) // Returns 6

Approach 1: Set Conversion (Simplest for Unsorted)

Most readable solution using JavaScript's built-in Set:

function countUniqueValues(arr) {
  return new Set(arr).size;
}

Approach 2: Hash Map Solution

function countUniqueValues(arr) {
  if (!arr.length) return 0;

  const seen = {};
  for (const num of arr) {
    seen[num] = true; // Mark value as seen
  }
  return Object.keys(seen).length;
};

Explanation:

1. Uses an object uniques to track seen values
2. Return the amount of keys

Performance analysis

• Time: O(n) - Single pass through the array
• Space: O(n) - Stores all unique values in worst case

Approach 3: Two-Pointer Technique

function countUniqueValues(arr) {
  if (!arr.length) return 0;
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }

  return i + 1;
}

Explanation:

1. Pointer i tracks the last unique value's position
2. Pointer j scans ahead for new values
3. When arrj differs from arri, it's a new unique value
4. Copy it to position i+1 to remove duplicates
5. Increment i
6. First i+1 elements become all unique values

Performance analysis

• Time: O(n) Single pass through array
• Space: O(1) We mutate the array

Why Sorting Matters

The two-pointer technique requires sorted input because it relies on these key properties:

1. Duplicate Grouping: Identical values are consecutive in sorted arrays
2. Single Pass Detection: New values appear immediately after all duplicates
3. In-Place Modification: Allows O(1) space complexity by overwriting duplicates

Without sorting, duplicates may be scattered, breaking the algorithm's core logic.

Performance Comparison

*Assumes in-place sorting. If creating a new sorted array, space becomes O(n).

Conclusion

That's it for the counting unique values algorithm. I hope you learned as much as I did. If you have any questions or suggestions, please hit me up !