Day 4/90: Conquering Duplicates in Sorted Arrays

The Challenge:
As I continue my 90-day DSA journey, today's battlefield was removing duplicates from a sorted array. The mission seemed simple at first glance, but required careful strategy to execute efficiently.

Why This Matters:
Duplicate removal is fundamental for:

  • Data cleaning and preprocessing
  • Optimizing storage space
  • Preparing data for other algorithms

My Battle Plan:
After analyzing the problem, I chose the two-pointer technique because:

  1. The array is already sorted (duplicates are adjacent)
  2. We need O(1) space complexity
  3. It allows single-pass operation (O(n) time)

The Solution:
Here's how I implemented the two-pointer approach:

'''typescript
function removeDuplicates(nums: number[]): number {
if (nums.length === 0) return 0;

let uniquePointer = 0;

for (let scout = 1; scout < nums.length; scout++) {
    if (nums[scout] !== nums[uniquePointer]) {
        uniquePointer++;
        nums[uniquePointer] = nums[scout];
    }
}

return uniquePointer + 1;

}
'''

How It Works:

  1. uniquePointer marks the end of our unique elements section
  2. scout looks ahead for the next unique element
  3. When we find a new unique element, we:
    • Move uniquePointer forward
    • Place the new element in its position

Visual Walkthrough:
For input [1,1,2,3,3]:

  1. Initial: [1,1,2,3,3], uniquePointer=0, scout=1
  2. First unique found: [1,2,2,3,3], uniquePointer=1
  3. Second unique found: [1,2,3,3,3], uniquePointer=2
  4. Final result: 3 unique elements [1,2,3,...]

Performance Analysis:

  • Time Complexity: O(n) - Single pass through array
  • Space Complexity: O(1) - No additional storage needed

Key Insights:

  1. The sorted property is crucial - random order would require different approach
  2. We're effectively compressing the unique elements to the front
  3. The remaining elements after our uniquePointer don't need to be cleared

Common Pitfalls:

  1. Forgetting to handle empty array case
  2. Off-by-one errors in the return value
  3. Unnecessary swaps when elements are equal

Testing Your Solution:
Always test these edge cases:

  • Empty array
  • All duplicates
  • No duplicates
  • Single element array

Going Further:
Try modifying this to:

  1. Allow at most 2 duplicates
  2. Work with unsorted arrays
  3. Return the modified array instead of just count

Final Thoughts:
This problem was an excellent exercise in efficient array manipulation. The two-pointer technique is powerful and appears in many other problems - well worth mastering!

Next Challenge:
Day 5 will tackle merging two sorted arrays - another practical application of similar techniques.

Discussion Question:
What other problems can benefit from this two-pointer approach? Share your thoughts below!