Problem Description
LeetCode 26. Remove Duplicates from Sorted Array
Algorithm to remove duplicates from a sorted array and return the value of the remaining elements.
Solution
Approach: Two Pointer
Used Two Pointer to adjust two indices, left and right, while removing duplicate values.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Approach: Two Pointer
#0011122334
ij <- If i and j are the same
i j <- Only move j up by 1
#0011122334 <- If i and j are different
ij <- Move i up by 1
#0101122334 <- Swap the two values
i j <- Move j up by 1
#0101122334 <- Swap the two values
i j <- If i and j are the same, move j up by 1
i j <- If i and j are different
i j <- Move i up by 1
#0121102334 <- Swap the two values
... <- Repeat this process
By moving i and j as described above, duplicate values are removed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
j = 1
cnt = 1
while i < len(nums) and j < len(nums):
if nums[i] == nums[j]:
j += 1
else:
i += 1
nums[i], nums[j] = nums[j], nums[i]
j += 1
cnt += 1
return cnt
The time and space complexity of the above solution are as follows:
- Time Complexity: O(N)
- It takes time proportional to the size of nums.
- Space Complexity: O(1)
- Only a few simple variables are used, resulting in O(1) space complexity.