Remove Duplicates from Sorted Array
Problem statement
You are given an array nums sorted in non-decreasing order. Remove the duplicate values in place — without allocating a new array — so that every value appears only once, and the remaining values keep their original order.
You can't shrink the array's length, so instead you overwrite the front of it with the unique values and return k, the count of unique values. A grading harness then checks that the first k slots match the expected unique values; anything after index k - 1 is ignored, so you don't need to clean it up.
Examples
Example 1
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: The unique values are 1 and 2, so k = 2. The first two slots hold 1 and 2; what's left in the third slot doesn't matter.
Example 2
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: There are five unique values (0, 1, 2, 3, 4), so k = 5. The first five slots hold them in order; the rest of the array is ignored.
Hints
Approach
Optimal: Two pointers
Intuition
You don't need a second array at all. Since duplicates are always neighbours in a sorted array, keep two markers: read scans every value from left to right, and write points at the next empty slot for a unique value. Whenever read finds a value that differs from the last value you kept, you copy it into write and move write forward. This overwrites the array with unique values as you go, using no extra memory — which is what makes it faster in space than the extra-array approach above.
Steps
- If
numsis empty, return 0. - Set
write = 1(index 0 is always kept — the first value is unique by definition). - For
readfrom 1 to the end ofnums:- If
nums[read]is different fromnums[write - 1](the last value kept), copynums[read]intonums[write]and incrementwrite. - Otherwise, it's a duplicate — skip it and move
readon.
- If
- Return
writeask.
Dry run
nums = [0, 0, 1, 1, 1, 2]
index: 0 1 2 3 4 5start: [0, 0, 1, 1, 1, 2] ^write=1 read=1: nums[1]=0 == nums[write-1]=0 -> duplicate, skipread=2: nums[2]=1 != nums[write-1]=0 -> keep: nums[1]=1, write=2 [0, 1, 1, 1, 1, 2]read=3: nums[3]=1 == nums[write-1]=1 -> duplicate, skipread=4: nums[4]=1 == nums[write-1]=1 -> duplicate, skipread=5: nums[5]=2 != nums[write-1]=1 -> keep: nums[2]=2, write=3 [0, 1, 2, 1, 1, 2] loop ends -> return k = write = 3first k slots: [0, 1, 2] (the rest is ignored)read always moves one step at a time and write only moves when a new unique value is found, so write never runs ahead of read — it's always copying from a position it has already passed.
Edge cases: a one-element array skips the loop entirely and returns k = 1; an array where every value is identical never advances write past 1, correctly returning k = 1.
Complexity
Time O(n) - `read` walks the array exactly once, from index 1 to the end, and every step does a single O(1) comparison and, at most, one swap, so the total work is O(n).
Space O(1) - The array is rewritten in place using only the two integer markers `read` and `write`. No second array, set, or list is allocated.
class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
if __name__ == "__main__":
nums1 = [1, 1, 2]
k1 = Solution().removeDuplicates(nums1)
print(k1, nums1[:k1])
nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k2 = Solution().removeDuplicates(nums2)
print(k2, nums2[:k2])RecapThe whole problem in a few lines, for the night before
- Spot it: remove repeats from a sorted array in place and return the new length
- Idea: a slow pointer marks the end of the unique part; a fast pointer scans, and each value different from the last unique one is copied to slow + 1
- Cost: O(n) time, O(1) space
- Trap: this only works because the array is sorted, so equal values sit next to each other
Interview follow-ups
What if the array wasn't sorted?
The neighbour trick stops working, because two equal values could be anywhere in the array. You'd need a hash set to remember every value seen so far, checking and inserting as you scan — still O(n) time, but now O(n) space, and you lose the in-place, O(1)-extra-memory property that sorting gave you for free.
Allow each value to appear at most twice instead of once (LeetCode 80).
Compare each candidate value not to
nums[write - 1]but tonums[write - 2]— that lets a value through as long as it wouldn't create a third copy in a row. Everything else about the two-pointer scan stays the same: same O(n) time, same O(1) extra space, just a one-line change to the comparison.
Frequently asked questions
In most languages you can't actually shrink an array's allocated size from inside a function — the caller owns that memory. Returning k and leaving the rest of the array alone is the standard workaround: the caller (here, the judge) only looks at the first k slots and ignores everything after them, so the values beyond index k - 1 genuinely don't matter.
A set would work for finding the unique values, but it wouldn't preserve order on its own in every language, and it still needs O(n) extra memory — no better than the extra-array approach above. Since the array is already sorted, the two-pointer scan gets the same result with no extra structure at all, which is strictly better.
Deduplicating a sorted list in place comes up whenever memory is tight — collapsing a sorted list of server IDs, timestamps, or log keys into their unique values without allocating a second buffer. The read/write two-pointer pattern here is the same one used to compact any buffer in place, which is a common building block in systems code.
