1. Problem Statement (Simple Explanation):
You are given an integer array nums that is sorted in non-decreasing order.
You must:
Remove duplicates in-place so that each unique element appears only once.
Keep the relative order of unique elements.
Return k, the number of unique elements.
After your function:
The first k elements of nums should contain the unique elements in sorted order.
Anything beyond index k - 1 can be ignored.
You must use only constant extra space O(1).
2. Examples:
Example 1:
Input: nums = [1,1,2]
Unique elements are [1,2].
Output: k = 2, nums = [1,2,_]
(Underscore means “don’t care” beyond k.)
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Unique elements: [0,1,2,3,4].
Output: k = 5, nums = [0,1,2,3,4,_,_,_,_,_]
Constraints:
1 <= nums.length <= 3 x 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.
3. Approach – Two Pointers (Slow/Fast) In-Place:
Because the array is sorted, duplicates are grouped together. We can use two pointers:
i (slow pointer): position of last unique element.
j (fast pointer): current position we’re scanning.
Intuition:
Start with the first element as unique.
Traverse from left to right:
If nums[j] != nums[i], we found a new unique element:
Move i one step to the right.
Copy nums[j] to nums[i].
If nums[j] == nums[i], it’s a duplicate, skip it.
At the end:
The first i + 1 elements of nums are the unique values.
Return i + 1 as k.
Algorithm (Step-by-Step):
If nums.length == 0 (not needed per constraints, but safe), return 0.
Initialize:
i = 0 (index of last unique element).
For j from 1 to n - 1:
If nums[j] != nums[i]:
i++
nums[i] = nums[j].
After the loop, the number of unique elements is i + 1.
Return i + 1.
Pseudo-code:
Let n = len(nums):
Time: O(n)
Each element is visited once.
Space: O(1)
In-place, only a few extra variables.
4. Java code:
6. C++ code:
7. Python code:
8. JavaScript code:
Comments
Post a Comment