40% off Premium for a limited time
InterviewLegend

Remove Duplicates from Sorted Array

Alex Chen15 min readEasy
In this lesson
  • Learn the same direction (read/write) two pointer pattern
  • Understand in-place array modification
  • Apply the pattern to remove unwanted elements

A sorted array hands you the duplicates for free: every repeat sits directly next to the value it copies. So you never reach for a hash set here, and you never allocate a second array. Two pointers moving the same direction finish the job in one pass, which is the thing that separates this from the converging pointers you used in Two Sum II. One pointer reads ahead. The other tracks where the next keeper belongs, and that read/write split is how you rewrite an array in place without spending a byte of extra space.

Step 1: Understand the Read/Write Pattern

The two cursors behave like editing a document. One reads through the text (the read pointer); the other marks where the next kept character lands (the write pointer). The read cursor touches every position, but the write cursor only advances once you've decided the thing you just read is worth keeping.

The invariant: Everything before the write pointer is "clean", with no duplicates. The read pointer explores ahead to find the next unique element.

[0, 1, 2 | ... unprocessed ...]
↑ write pointer (first 3 elements are unique)

Step 2: The Algorithm

The whole loop is this:

python
write = 0  # Points to last unique element we've written
for read in range(1, len(nums)):
    if nums[read] != nums[write]:
        # Found a new unique element!
        write += 1           # Advance write position
        nums[write] = nums[read]  # Copy the unique element
return write + 1  # Count of unique elements

Why compare with nums[write] instead of nums[read-1]? Because nums[write] is always the last unique value we kept. After processing, everything from 0 to write is unique. The original value at read-1 might be a duplicate we skipped!

Step 3: Visual Walkthrough

Initial State
Both pointers start at index 0. First element is always unique.
0
0
1
1
2
0
1
2
3
4
W
Write=0, Read=0

Try It Yourself

The write pointer only advances when the read pointer finds something different from nums[write]. Return write + 1 (index → count).

Try it yourself

Remove Duplicates

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once.

The relative order of the elements should be kept the same. Return k after placing the final result in the first k slots of nums.

Constraints:
• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order

Examples

Input: nums = [1, 1, 2]

Output: 2, nums = [1, 2, _]

Return k=2. First two elements are unique values 1 and 2.

Input: nums = [0,0,1,1,1,2,2,3,3,4]

Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Return k=5. Five unique values remain.

Remove Duplicates

Loading...
Click "Run" to execute your code

Test Cases

Input: [1, 1, 2]Expected: 2
Input: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]Expected: 5
Input: [1]Expected: 1

Solution

def solution(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Time: O(log n) | Space: O(1)

Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Things to Watch Out For

A few mistakes that come up more often than you'd think:

1. Off-by-one on the return value: The write pointer is 0-indexed, but the problem wants a count. Return write + 1 so the index becomes a count.

2. Comparing with nums[read-1] instead of nums[write]: After overwriting elements, nums[read-1] might hold a value you already wrote. Always compare with nums[write] to check the last kept unique value.

3. Edge cases: Empty array → return 0. Single element → return 1. All duplicates like [7, 7, 7, 7] → write never advances past 0, return 1.

The Read/Write Pattern

One reads, one writes. That split is the workhorse behind almost every in-place array edit. The write pointer owns the clean portion of the array while the read pointer scouts ahead, and swapping in a different keep-condition is all it takes to solve a whole family of these: Remove Element drops one specific value, Remove Duplicates II tolerates two copies of each.

Key Takeaways

  • Same direction pointers: one reads, one writes
  • Write pointer only advances when we find something to keep
  • Sorted array makes duplicates adjacent (easy to detect)
  • Return write + 1 for the count
  • Pattern adapts: change the "should I keep this?" condition
Next: Premium lesson