Problem Description
LeetCode 80. Remove Duplicates from Sorted Array II
Remove duplicates from the array, keeping at most two occurrences of each element.
Solution
Approach: Two Pointer
I used two pointers to adjust the indices and solve the problem following the logic below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Approach: Two Pointer
#111223
ij <- If equal, it's the first duplicate
ij <- If equal, increment the duplicate count
ij <- If duplicate count is 2 or more, only increment j
i j <- If different element is found
ij <- Increment i
#112123 <- Swap
i j <- If equal and duplicate count is less than 2
ij
#112213
ij
i j <- If different element is found
ij <- Increment i
#112231 <- Swap
ij <- If different element is found
i/j <- Increment i and swap
j <- j reached the end
Moving the indices i and j according to the above logic ensures that only up to two duplicates are retained, and the rest are removed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# Return 0 if nums is empty
if not nums:
return 0
i = 0
j = 1
dup = 1
while i < len(nums) and j < len(nums):
# If items are equal
if nums[i] == nums[j]:
# If no consecutive items, increment i and swap with j
if dup < 2:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
# If consecutive items exist, increment j and increase dup
j = j + 1
dup += 1
else:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
j = j + 1
dup = 1
return i + 1
The time and space complexity of the above solution are as follows:
- Time Complexity: O(N)
- There is a loop for nums, resulting in O(N) time complexity.
- Space Complexity: O(1)
- No additional space is used.