21. Remove Duplicates from Sorted Array
🔗 LeetCode Problem: 26. Remove Duplicates from Sorted Array
📊 Difficulty: Easy
🏷️ Topics: Array, Two Pointers
Problem Statement
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. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
- Change the array
numssuch that the firstkelements ofnumscontain the unique elements in the order they were present innumsinitially. - The remaining elements of
numsare not important as well as the size ofnums. - Return
k.
Custom Judge:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
- 1 <= nums.length <= 3 * 10^4
- -100 <= nums[i] <= 100
- nums is sorted in non-decreasing order
🎨 Visual Understanding
The Problem Visualized
Input: nums = [1, 1, 2, 2, 2, 3]
Goal: Keep only unique elements in the first k positions
Before: [1, 1, 2, 2, 2, 3]
After: [1, 2, 3, _, _, _]
└──k=3──┘
Return: k = 3
In-Place Modification
"In-place" means:
- Modify the original array
- Don't create a new array
- Use only O(1) extra space
Example transformation:
[1, 1, 2, 2, 2, 3]
↓
[1, 2, 3, 2, 2, 3] ← First 3 elements are unique
└─k=3─┘
The Two Pointer Strategy
Use two pointers:
- i: slow pointer (position to place next unique element)
- j: fast pointer (scanning through array)
[1, 1, 2, 2, 2, 3]
i j
When nums[j] != nums[i]:
Move unique element to position i+1
Advance i
[1, 1, 2, 2, 2, 3]
i j
nums[j]=2 != nums[i]=1 → place 2 at i+1
[1, 2, 2, 2, 2, 3]
i j
Continue until j reaches end
🎯 Approach 1: Using Extra Space (Not Allowed)
The Most Natural Thinking 💭
Core Logic:
Use a Set or new array to collect unique elements:
1. Iterate through array
2. Add unique elements to Set
3. Copy back to original array
Or create new array with uniques
Why This Works: - Set automatically handles duplicates - Easy to understand - Straightforward implementation
Why This is NOT Valid: - Problem requires in-place modification - O(n) extra space violates constraint - Not the solution we need
Implementation (For Understanding Only)
// NOT VALID - Uses extra space
public int removeDuplicates(int[] nums) {
Set<Integer> unique = new LinkedHashSet<>();
for (int num : nums) {
unique.add(num);
}
int i = 0;
for (int num : unique) {
nums[i++] = num;
}
return unique.size();
}
⏰ Time: O(n)
💾 Space: O(n) - violates constraint
✅ Approach 2: Two Pointers (Optimal)
The Breakthrough Insight 💡
Core Logic:
Key observation: Array is already sorted!
Duplicates are adjacent.
Strategy using two pointers:
- i: Points to position of last unique element
- j: Scans through array
Algorithm:
1. Start i at 0 (first element always unique)
2. For j from 1 to n-1:
- If nums[j] != nums[i] → found new unique!
- Place it at position i+1
- Increment i
3. Return i+1 (number of unique elements)
Why This Works:
Since array is sorted, duplicates are consecutive:
[1, 1, 1, 2, 2, 3]
└─same─┘ └same┘
We only need to compare adjacent elements!
nums[j] != nums[i] means we found a new unique value.
Visual Process:
[1, 1, 2, 2, 2, 3]
i j
j=1: nums[1]=1 == nums[0]=1 → skip
j=2: nums[2]=2 != nums[0]=1 → unique!
i++, nums[1] = nums[2]
[1, 2, 2, 2, 2, 3]
i j
j=3: nums[3]=2 == nums[1]=2 → skip
j=4: nums[4]=2 == nums[1]=2 → skip
j=5: nums[5]=3 != nums[1]=2 → unique!
i++, nums[2] = nums[5]
[1, 2, 3, 2, 2, 3]
i j
Return i+1 = 3
Why This is Better: - O(n) time - single pass - O(1) space - only two pointers - In-place modification - Optimal solution!
Implementation
public int removeDuplicates(int[] nums) {
// Edge case: empty array
if (nums.length == 0) return 0;
// i points to position of last unique element
int i = 0;
// j scans through array
for (int j = 1; j < nums.length; j++) {
// Found a new unique element
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
// Return count of unique elements
return i + 1;
}
Step-by-Step Execution: nums = [0,0,1,1,1,2,2,3,3,4]
Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
i = 0 (position of last unique)
j=1: nums[1]=0
═══════════════════════════════════════════════════════════════════
Compare: nums[1]=0 vs nums[0]=0
Same → skip (duplicate)
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
i j
j=2: nums[2]=1
═══════════════════════════════════════════════════════════════════
Compare: nums[2]=1 vs nums[0]=0
Different → unique!
i++ → i=1
nums[1] = nums[2] = 1
nums = [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
i j
j=3: nums[3]=1
═══════════════════════════════════════════════════════════════════
Compare: nums[3]=1 vs nums[1]=1
Same → skip
nums = [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
i j
j=4: nums[4]=1
═══════════════════════════════════════════════════════════════════
Compare: nums[4]=1 vs nums[1]=1
Same → skip
nums = [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
i j
j=5: nums[5]=2
═══════════════════════════════════════════════════════════════════
Compare: nums[5]=2 vs nums[1]=1
Different → unique!
i++ → i=2
nums[2] = nums[5] = 2
nums = [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
i j
j=6: nums[6]=2
═══════════════════════════════════════════════════════════════════
Compare: nums[6]=2 vs nums[2]=2
Same → skip
nums = [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
i j
j=7: nums[7]=3
═══════════════════════════════════════════════════════════════════
Compare: nums[7]=3 vs nums[2]=2
Different → unique!
i++ → i=3
nums[3] = nums[7] = 3
nums = [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
i j
j=8: nums[8]=3
═══════════════════════════════════════════════════════════════════
Compare: nums[8]=3 vs nums[3]=3
Same → skip
nums = [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
i j
j=9: nums[9]=4
═══════════════════════════════════════════════════════════════════
Compare: nums[9]=4 vs nums[3]=3
Different → unique!
i++ → i=4
nums[4] = nums[9] = 4
nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
i j
Loop ends
═══════════════════════════════════════════════════════════════════
Return i + 1 = 4 + 1 = 5
Final array: [0, 1, 2, 3, 4, _, _, _, _, _]
└────k=5────┘
🎯 RESULT: k = 5
═══════════════════════════════════════════════════════════════════
Another Example: nums = [1,1,2]
Initial: nums = [1, 1, 2], i = 0
j=1: nums[1]=1 vs nums[0]=1 → same, skip
nums = [1, 1, 2]
i j
j=2: nums[2]=2 vs nums[0]=1 → different!
i++ → i=1
nums[1] = nums[2] = 2
nums = [1, 2, 2]
i j
Return i+1 = 2
Result: [1, 2, _]
Example: All Same: nums = [1,1,1,1]
Initial: i=0
j=1,2,3: All equal to nums[0]=1 → skip
i stays at 0
Return i+1 = 1
Result: [1, _, _, _]
Example: All Unique: nums = [1,2,3,4]
Initial: i=0
j=1: 2!=1 → i=1, nums[1]=2 → [1,2,3,4]
j=2: 3!=2 → i=2, nums[2]=3 → [1,2,3,4]
j=3: 4!=3 → i=3, nums[3]=4 → [1,2,3,4]
Return i+1 = 4
Result: [1, 2, 3, 4]
⏰ Time: O(n) - single pass through array
💾 Space: O(1) - only two pointers
🔍 Edge Cases
Case 1: Single element
Input: nums = [1]
Output: 1, nums = [1]
Strategy: No duplicates, return 1
Case 2: Two same elements
Input: nums = [1,1]
Output: 1, nums = [1,_]
Case 3: Two different elements
Input: nums = [1,2]
Output: 2, nums = [1,2]
Case 4: All same elements
Input: nums = [5,5,5,5,5]
Output: 1, nums = [5,_,_,_,_]
Case 5: All unique elements
Input: nums = [1,2,3,4,5]
Output: 5, nums = [1,2,3,4,5]
Case 6: Negative numbers
Input: nums = [-3,-1,-1,0,0,0,1]
Output: 4, nums = [-3,-1,0,1,_,_,_]
Case 7: Many duplicates at start
Input: nums = [1,1,1,1,2]
Output: 2, nums = [1,2,_,_,_]
Case 8: Many duplicates at end
Input: nums = [1,2,2,2,2]
Output: 2, nums = [1,2,_,_,_]
Common Mistakes
Mistake 1: Starting j from 0 instead of 1
❌ Wrong: for (int j = 0; j < nums.length; j++)
✓ Right: for (int j = 1; j < nums.length; j++)
Reason: First element always unique
Mistake 2: Incrementing i before assignment
❌ Wrong:
i++;
if (nums[j] != nums[i]) {
nums[i] = nums[j];
}
✓ Right:
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
Mistake 3: Returning i instead of i+1
❌ Wrong: return i;
✓ Right: return i + 1;
Reason: i is index, count is i+1
Mistake 4: Not handling empty array
❌ Wrong: Don't check if array empty
✓ Right: if (nums.length == 0) return 0;
Mistake 5: Comparing with previous element
❌ Wrong: if (nums[j] != nums[j-1])
✓ Right: if (nums[j] != nums[i])
Reason: Need to compare with last unique, not just previous
Mistake 6: Creating new array
❌ Wrong: int[] result = new int[nums.length];
✓ Right: Modify nums in-place
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Extra Space (HashSet/Array)
Time: O(n)
Space: O(n)
Use: Violates in-place requirement
Approach 2: Two Pointers (OPTIMAL)
Time: O(n)
Space: O(1)
Use: Best solution, meets all requirements
🔑 The Core Insight
Problem: Remove duplicates in-place from sorted array
Key observation: Array is sorted!
→ Duplicates are consecutive
→ Only need to compare adjacent elements
→ Use two pointers to overwrite duplicates
Two pointer pattern:
→ i: position to place next unique element
→ j: scans through array looking for uniques
→ When nums[j] != nums[i]: found unique, place at i+1
Why it works:
→ Sorted array → duplicates are adjacent
→ We maintain unique elements in first i+1 positions
→ Order is preserved
🎯 Pattern Recognition
Problem Type: In-Place Array Modification
Core Pattern: Two Pointers (Fast & Slow)
When to Apply:
✓ Array is sorted
✓ Need to remove/modify elements in-place
✓ O(1) space required
✓ Relative order must be preserved
Key Techniques:
→ Fast pointer (j) scans array
→ Slow pointer (i) tracks last valid position
→ Overwrite duplicates with unique elements
→ Return count based on slow pointer
Related Problems:
- Remove Duplicates from Sorted Array II (LC 80)
- Remove Element (LC 27)
- Move Zeroes (LC 283)
- Remove Duplicates from Sorted List (LC 83)
🧠 Interview Strategy
Step 1: "Need to remove duplicates in-place from sorted array"
Step 2: "Key insight: array is sorted, duplicates are adjacent"
Step 3: "Use two pointers - slow (i) and fast (j)"
Step 4: "When different values found, copy to i+1"
Step 5: "Return i+1 as count of unique elements"
📝 Quick Revision Notes
🎯 Core Concept:
Use two pointers on sorted array. Slow pointer (i) tracks last unique position. Fast pointer (j) scans for new unique values. When found, place at i+1.
⚡ Quick Implementation:
public int removeDuplicates(int[] a) {
// Using 2 pointers
int i = 0;
int j = 0;
int len = a.length;
while(i < len && j < len) {
// proceed till a[i] and a[j] are not equal
// initializing i and j at 0.
while (j< len && a[i] == a[j]) {
j++;
}
// once they are not equal, move i to next index.
i++;
// swap (move) if i an j are not equal
if(j < len && i != j) {
// move number at index j to index i
a[i] = a[j];
}
}
return i;
}
🔑 Key Insights:
- Sorted array: duplicates are consecutive
- Two pointers: i (slow/write), j (fast/read)
- Start j at 1: first element always unique
- Compare nums[j] with nums[i]: not nums[j-1]
- When different: increment i, then copy
- Return i+1: count of uniques (index to count)
- In-place: O(1) extra space
- Single pass: O(n) time complexity
🎪 Memory Aid:
"Slow writes uniques, fast finds them!"
Think: "i writes, j reads, different → copy and advance"
Related Patterns
- Remove Duplicates from Sorted Array II (LC 80)
- Remove Element (LC 27)
- Move Zeroes (LC 283)
- Remove Duplicates from Sorted List (LC 83)
Happy practicing! 🎯