26. Remove Duplicates from Sorted Array
Asked at Google, Amazon, Meta, Oracle and 1 more
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Array
Companies
5
Problem
You get an integer array nums that is already sorted in non-decreasing order (each element is greater than or equal to the one before it). Your job is to remove the duplicate values in place, so that every distinct value appears exactly once, and the values stay in the same sorted order.
Because the array is sorted, equal values always sit next to each other. That means you can solve this with two pointers and no extra array. One pointer (write) marks the end of the cleaned-up part. The other pointer (read) walks through the whole array. When nums[read] is different from the value at write, you have found a new unique value, so you copy it to the next free slot.
Return k, the number of unique values. The first k positions of nums must hold those unique values in order. Whatever is left after index k - 1 does not matter — the judge ignores it. You must use O(1) extra memory, so a hash set or a second array is not allowed.
Keep one copy of each value
Constraints
- ●
1 <= nums.length <= 3 * 10^4 - ●
-100 <= nums[i] <= 100 - ●
nums is sorted in non-decreasing order
Examples
nums = [1,1,2]2, nums = [1,2,_]nums = [0,0,1,1,1,2,2,3,3,4]5, nums = [0,1,2,3,4,_,_,_,_,_]Asked At
5 companies| 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 → |
| Bloomberg | Easy | View all Bloomberg 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.
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.
Two pointers: write and read
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Remove Duplicates from Sorted Array?
Remove Duplicates from Sorted Array is asked at Google, Amazon, Meta, Oracle, Bloomberg. 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.