Remove Duplicates from Sorted Array
Asked at Google, Amazon, Meta, Oracle
Problem
Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length. You must use O(1) extra memory. This problem tests your understanding of two pointers for in-place array modification.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Meta | Easy | View all Meta questions → |
| Oracle | Easy | View all Oracle questions → |
How to Think About It
Brute force: use a hash set to track seen elements and build a new array. That works but uses O(n) extra space. The problem requires O(1) extra space.
Key insight: since the array is sorted, duplicates are always adjacent. Use two pointers: a "write" pointer (slow) and a "read" pointer (fast). The read pointer scans every element. The write pointer only advances when a new (non-duplicate) element is found.
The pattern: both pointers start at index 0. The read pointer always moves forward. When nums[read] != nums[write], copy nums[read] to nums[write + 1] and advance the write pointer. After the scan, write + 1 is the new length.
Visual walkthrough for [1, 1, 2, 3, 3]:
write=0, read=0: nums[0]==nums[0] (1==1). read advances.
write=0, read=1: nums[1]==nums[0] (1==1). read advances.
write=0, read=2: nums[2]!=nums[0] (2!=1). Copy nums[2] to nums[1]. write=1.
write=1, read=3: nums[3]!=nums[1] (3!=2). Copy nums[3] to nums[2]. write=2.
write=2, read=4: nums[4]==nums[2] (3==3). read advances.
Done. write+1 = 3. Array starts with [1, 2, 3, ...]
Edge cases: empty array returns 0. Single element returns 1. All elements are the same returns 1. No duplicates returns original length.
Optimal Approach
Step 1: Initialize write = 0.
Step 2: For read from 1 to end of array:
- If
nums[read]!=nums[write], increment write and setnums[write]=nums[read]
Step 3: Return write + 1.
Walkthrough for [1, 1, 2, 3, 3]:
- write=0, read=1: 1 == 1, skip.
- write=0, read=2: 2 != 1, write=1, nums[1]=2. Array: [1, 2, 2, 3, 3]
- write=1, read=3: 3 != 2, write=2, nums[2]=3. Array: [1, 2, 3, 3, 3]
- write=2, read=4: 3 == 3, skip.
- Return write+1 = 3. The first 3 elements [1, 2, 3] are the unique sorted elements.
Time: O(n) -- one pass through the array. Space: O(1) -- only two pointers, no extra data structures.
What Trips People Up in Real Interviews
Using a hash set to remove duplicates. This works but uses O(n) extra space. The problem explicitly requires O(1) extra memory. The two pointers approach is the correct in-place solution.
Not understanding what "return the new length" means. The problem doesn't ask you to truncate the array -- just return the length. The caller uses that length to access the valid portion of the array.
Starting both pointers at index 1 instead of having read start at 1 and write at 0. Starting both at 0 means you're comparing an element with itself, which always matches -- you'll never advance the write pointer.
Forgetting that the array is sorted. The sorted property guarantees duplicates are adjacent. If the array weren't sorted, this two-pointer approach wouldn't work -- you'd need a hash set or sorting first.
Returning write instead of write + 1. The write pointer points to the last unique element, so the length is write + 1 (1-indexed). This off-by-one error is the most common mistake.
Solution Code
def removeDuplicates(nums):
if not nums:
return 0
write = 0
for read in range(1, len(nums)):
if nums[read] != nums[write]:
write += 1
nums[write] = nums[read]
return write + 1Frequently Asked Questions
What is the Remove Duplicates from Sorted Array problem?
Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length. You must use `O(1)` extra memory. This problem tests your understanding of `two pointers` for in-place array modification.
How do you solve Remove Duplicates from Sorted Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Remove Duplicates from Sorted Array?
Remove Duplicates from Sorted Array is asked at Google, Amazon, Meta, Oracle. It is a easy difficulty problem.
What are common mistakes on Remove Duplicates from Sorted Array?
- Using a `hash set` to remove duplicates. This works but uses `O(n)` extra space. The problem explicitly requires `O(1)` extra memory. The `two pointers` approach is the correct in-place solution.
- Not understanding what "return the new length" means. The problem doesn't ask you to truncate the array -- just return the length. The caller uses that length to access the valid portion of the array.
- Starting both pointers at index 1 instead of having read start at 1 and write at 0. Starting both at 0 means you're comparing an element with itself, which always matches -- you'll never advance the write pointer.
- Forgetting that the array is sorted. The sorted property guarantees duplicates are adjacent. If the array weren't sorted, this two-pointer approach wouldn't work -- you'd need a `hash set` or sorting first.
- Returning write instead of write + 1. The write pointer points to the last unique element, so the length is write + 1 (1-indexed). This off-by-one error is the most common mistake.