You are given an integer array nums sorted in non-decreasing order. Remove the repeated values in place so each distinct value appears once, keeping their original order. Return k, the number of distinct values; the first k positions of nums must hold them. What is left after position k does not matter.
- 1 <= nums.length <= 3 * 10^4
- -100 <= nums[i] <= 100
- `nums` is sorted in non-decreasing order
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Building a new list of distinct values is easy but uses O(n) extra space, and the task asks for in place. Since the array is sorted, a value is new exactly when it differs from the last value we kept. A slow write pointer marks the end of the kept part and a fast read pointer scans ahead, so one pass with O(1) space is enough.
Algorithm
- Set
k = 1(the first element is always kept). - For
ifrom 1 ton - 1, comparenums[i]withnums[k - 1]. - If they differ, write
nums[k] = nums[i]and increasek. - Return
k.
O(n)Space: O(1)nums[k - 2] instead of nums[k - 1]. The same pattern works for any limit.class Solution: def removeDuplicates(self, nums: List[int]) -> int: k = 1 # nums[:k] holds the distinct values so far for i in range(1, len(nums)): if nums[i] != nums[k - 1]: nums[k] = nums[i] k += 1 return k