The two pointers technique is one of the most elegant and efficient patterns in programming. While we often think of two pointers as starting from opposite ends of an array and moving toward each other, there’s another powerful variation where both pointers start from the same side and move in the same direction at different speeds. Today, we’ll explore this technique by solving a classic problem: counting unique values in a sorted array.
Understanding the Problem
Let’s start with a clear problem statement:
Write a function called findUniqueCount that accepts a sorted array and returns the count of unique values in that array.
Here are some examples to illustrate what we’re trying to achieve:
findUniqueCount([2, 2, 4, 6, 6, 8]) // Should return 4 (values: 2, 4, 6, 8)
findUniqueCount([1, 3, 5, 7, 9, 11, 13]) // Should return 7 (all values are unique)
findUniqueCount([]) // Should return 0 (empty array)
findUniqueCount([-3, -1, -1, 0, 2, 2, 2]) // Should return 4 (values: -3, -1, 0, 2)
The Naive Approach vs. Two Pointers
Before diving into the two pointers solution, let’s consider what a naive approach might look like:
// Naive approach - using additional space
function findUniqueCountNaive(sortedArray) {
const uniqueSet = new Set(sortedArray);
return uniqueSet.size;
}
While this works, it uses extra space proportional to the number of unique elements. Can we do better?
The Two Pointers Approach Explained
The beauty of the two pointers technique for this problem lies in leveraging the fact that our array is already sorted. Since identical values are grouped together, we can use two pointers moving at different speeds to identify and count unique values efficiently.
The Core Concept
Think of our two pointers as:
- Slow pointer (
left): Points to the position where we’ll place the next unique value - Fast pointer (
right): Scouts ahead to find the next different value
Here’s the key insight: we can modify the original array in-place, building up a collection of unique values at the beginning of the array.
Step-by-Step Walkthrough
Let’s trace through an example with the array [3, 3, 5, 7, 7, 7, 9, 11, 11]:
Initial State:
Array: [3, 3, 5, 7, 7, 7, 9, 11, 11]
↑ ↑
left right
Step 1: Compare values at left and right
arr[left] = 3,arr[right] = 3→ They’re equal, so moverightforward
Step 2:
Array: [3, 3, 5, 7, 7, 7, 9, 11, 11]
↑ ↑
left right
arr[left] = 3,arr[right] = 5→ They’re different! Found a new unique value- Move
leftforward and place the new value:arr[++left] = arr[right]
Step 3:
Array: [3, 5, 5, 7, 7, 7, 9, 11, 11]
↑ ↑
left right
We continue this process until right reaches the end of the array.
Complete Implementation
Here’s the complete solution with detailed comments:
function findUniqueCount(sortedArray) {
// Handle edge case: empty array
if (sortedArray.length === 0) {
return 0;
}
// Initialize our slow pointer
let left = 0;
// Fast pointer starts from index 1
for (let right = 1; right < sortedArray.length; right++) {
// If we find a different value
if (sortedArray[left] !== sortedArray[right]) {
// Move slow pointer forward
left++;
// Place the new unique value at the slow pointer position
sortedArray[left] = sortedArray[right];
}
// If values are equal, we just continue (right pointer moves automatically)
}
// The count of unique values is left + 1 (since left is 0-indexed)
return left + 1;
}
Let’s Test Our Solution
// Test cases
console.log(findUniqueCount([2, 2, 4, 6, 6, 8])); // Output: 4
console.log(findUniqueCount([1, 3, 5, 7, 9, 11, 13])); // Output: 7
console.log(findUniqueCount([])); // Output: 0
console.log(findUniqueCount([-3, -1, -1, 0, 2, 2, 2])); // Output: 4
console.log(findUniqueCount([10])); // Output: 1
console.log(findUniqueCount([5, 5, 5, 5])); // Output: 1
Alternative Implementation: Without Modifying the Original Array
If you prefer not to modify the input array, here’s a variation that only counts without storing:
function countUniqueValues(sortedArray) {
if (sortedArray.length === 0) {
return 0;
}
let uniqueCount = 1; // First element is always unique
let left = 0;
for (let right = 1; right < sortedArray.length; right++) {
if (sortedArray[left] !== sortedArray[right]) {
uniqueCount++;
left = right; // Move left to the new unique value position
}
}
return uniqueCount;
}
Visual Example with Detailed Tracing
Let’s trace through [8, 8, 10, 12, 12, 15] step by step:
Initial: [8, 8, 10, 12, 12, 15]
↑ ↑
left right
Step 1: arr[0]=8, arr[1]=8 → Equal, move right
[8, 8, 10, 12, 12, 15]
↑ ↑
left right
Step 2: arr[0]=8, arr[2]=10 → Different!
left++ → left=1, arr[1]=10
[8, 10, 10, 12, 12, 15]
↑ ↑
left right
Step 3: arr[1]=10, arr[3]=12 → Different!
left++ → left=2, arr[2]=12
[8, 10, 12, 12, 12, 15]
↑ ↑
left right
Step 4: arr[2]=12, arr[4]=12 → Equal, move right
[8, 10, 12, 12, 12, 15]
↑ ↑
left right
Step 5: arr[2]=12, arr[5]=15 → Different!
left++ → left=3, arr[3]=15
[8, 10, 12, 15, 12, 15]
↑
left
Final result: left=3, so unique count = 3+1 = 4
Unique values stored: [8, 10, 12, 15]
Time and Space Complexity Analysis
Time Complexity: O(n)
- We traverse the array exactly once with our fast pointer
- Each element is examined at most twice (once by each pointer)
Space Complexity: O(1)
- We use only a constant amount of extra space
- The algorithm works in-place, modifying the original array
When to Use This Technique
This two pointers approach is ideal when:
- The array is sorted – This is crucial for the algorithm to work
- In-place modification is acceptable – We’re changing the original array
- You need optimal space complexity – No additional data structures required
- Linear time complexity is sufficient – Perfect for large datasets
Common Pitfalls and Edge Cases
1. Empty Array Handling
Always check for empty arrays first:
if (sortedArray.length === 0) return 0;
2. Single Element Array
Arrays with one element should return 1:
findUniqueCount([42]); // Should return 1
3. All Elements Same
findUniqueCount([7, 7, 7, 7]); // Should return 1
4. All Elements Different
findUniqueCount([1, 2, 3, 4]); // Should return 4
Practice Problems
Try solving these related problems using the two pointers technique:
- Remove Duplicates: Modify the array to contain only unique elements and return the new length
- Find Pairs with Target Sum: In a sorted array, find all pairs that sum to a target value
- Move Zeros: Move all zeros to the end while maintaining relative order of non-zero elements
Real-World Applications
This technique is commonly used in:
- Data preprocessing: Cleaning datasets by removing duplicates
- Database operations: Optimizing queries on sorted data
- Memory management: Efficient in-place array manipulation
- Algorithm interviews: A popular pattern in coding challenges
Conclusion
The two pointers technique for counting unique values demonstrates the power of leveraging array properties (in this case, being sorted) to create efficient algorithms. By using two pointers moving at different speeds, we achieve both optimal time complexity O(n) and space complexity O(1).
This pattern is particularly valuable because it teaches us to think creatively about pointer movement – not all two pointer problems require starting from opposite ends. Sometimes, the most elegant solution involves pointers that work together from the same starting point.
Remember: the key to mastering algorithmic patterns like this is practice and understanding the underlying principles. Once you grasp why this works, you’ll start recognizing similar opportunities in other problems.
Key Takeaways
- Two pointers don’t always start from opposite ends
- Sorted arrays enable powerful in-place algorithms
- Consider modifying input arrays when it’s acceptable to do so
- Always handle edge cases (empty arrays, single elements)
- Time complexity: O(n), Space complexity: O(1)
Keep practicing, and you’ll find that the two pointers technique becomes a natural part of your problem-solving toolkit!
