Number of unique elements in sorted array with repeated elements

Problem

Given a sorted array (possibly with repeated elements), find the number of unique elements in the array.

Follow up: How can you do it without using extra space?

Examples

Example 1

Input: [1, 1, 1, 2]
Output: 2
Explanation: Unique elements are 1 and 2.

Example 2

Input: [1, 1, 2]
Output: 2
Explanation: Unique elements are 1 and 2.

Solution

Method 1 – In-Place Adjacent Comparison

Intuition

Since the array is sorted, all duplicates are adjacent. We can count unique elements by comparing each element to its previous one.

Approach

1. If the array is empty, return 0.
2. Initialize a counter for unique elements (start at 1).
3. Iterate from the second element to the end:

• If the current element is different from the previous, increment the counter.

4. Return the counter.

Code

C++

class Solution {
public:
  int countUnique(vector<int>& arr) {
    if (arr.empty()) return 0;
    int ans = 1;
    for (int i = 1; i < arr.size(); ++i) {
      if (arr[i] != arr[i-1]) ans++;
    }
    return ans;
  }
};

Java

class Solution {
  public int countUnique(int[] arr) {
    if (arr.length == 0) return 0;
    int ans = 1;
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] != arr[i-1]) ans++;
    }
    return ans;
  }
}

Python

class Solution:
  def count_unique(self, arr: list[int]) -> int:
    if not arr:
      return 0
    ans = 1
    for i in range(1, len(arr)):
      if arr[i] != arr[i-1]:
        ans += 1
    return ans

Complexity

• ⏰ Time complexity: O(n) — Each element is checked once.
• 🧺 Space complexity: O(1) — No extra space is used.

Method 2 – Using HashSet

Intuition

Add each element to a set; the set size gives the number of unique elements.

Approach

1. Initialize an empty set.
2. Iterate through the array, adding each element to the set.
3. Return the size of the set.

Code

Java

class Solution {
  public int countUnique(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int num : arr) set.add(num);
    return set.size();
  }
}

Python

class Solution:
  def count_unique(self, arr: list[int]) -> int:
    return len(set(arr))

Complexity

• ⏰ Time complexity: O(n) — Each element is processed once.
• 🧺 Space complexity: O(n) — In the worst case, all elements are unique.