26. Remove Duplicates from Sorted Array #235
Description
Problem Number
26
Problem Title
Remove Duplicates from Sorted Array
LeetCode Link
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
- Edge Case Handling
First, handle the trivial case: if the array is empty or has only one element, there are no duplicates to remove, and its length is the answer.
-
Initialization
Initialize the write pointer k to 1. This pointer indicates the position to place the next unique element and will ultimately represent the length of the array with unique elements.
-
Iteration
Use the read pointer i to iterate through the array starting from the second element (i=1) up to the end.
-
Comparison and Writing
Inside the loop, compare the current element nums[i] (read pointer) with the element just before the write pointer nums[k-1].
If nums[i] != nums[k-1]: This means nums[i] is a unique element (since the array is sorted, we only need to compare it to the previous unique element). We write this unique element to the position pointed to by k: nums[k] = nums[i]. We increment the write pointer: k++. If nums[i] == nums[k-1]: This means nums[i] is a duplicate. We do nothing and simply let the read pointer i advance. The value at nums[k] remains untouched until a new unique element is found. -
Result
After the loop finishes, the first k elements of the array contain the unique elements in their original relative order.
Return k as the new length.
Intuition
Two Pointers Approach
The key insight that simplifies this problem is that the array is sorted. Since the array is sorted, all duplicate elements will be grouped together.
The goal is to modify the array in-place to contain only the unique elements in the beginning. We don't care about what values are beyond the new length.
We can use a Two-Pointers technique:
Read Pointer (i): This pointer iterates through the entire array from the second element (i=1) to read the values.
Write Pointer (k): This pointer keeps track of the position where the next unique element should be written. It starts at the second position (k=1), as the first element (nums[0]) is always unique in the resulting array.
The main idea is: If the element we are reading (nums[i]) is different from the last unique element we wrote (nums[k−1]), then it's a new unique element, and we should write it to the current position of the write pointer (nums[k]) and advance the write pointer (k).
Solution in C++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int insertIndex = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] != nums[i]) {
nums[insertIndex] = nums[i];
insertIndex++;
}
}
return insertIndex;
}
};