The "Remove Duplicates from Sorted Array" problem is a common LeetCode question. Here's a detailed explanation and solution.
Problem Description
Given a sorted array nums, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be maintained. Return the new length of the array.
You must modify the input array in place using O(1) extra memory.
Example
Example 1:
Input:
nums = [1, 1, 2]
Output:
2, nums = [1, 2, _]
Explanation: After removing duplicates, the first two elements of nums are unique. The length is 2. The _ represents irrelevant values beyond the new length.
Example 2:
Input:
nums = [0,0,1,1,1,2,2,3,3,4]
Output:
5, nums = [0, 1, 2, 3, 4, ...]
Explanation: The first five elements are unique.
Solution: Two Pointer Technique
python
Copy code
def removeDuplicates(nums):
if not nums: # If the array is empty
return 0
# Initialize two pointers
i = 0 # Slow pointer
for j in range(1, len(nums)): # Fast pointer
if nums[j] != nums[i]: # Found a new unique element
i += 1
nums[i] = nums[j] # Update the position of the slow pointer
return i + 1 # Length of the unique array
Explanation of the Approach:
Use two pointers:
i: Tracks the position of the last unique element.
j: Iterates through the array.
When a new unique element is found (nums[j] != nums[i]), move i forward and update nums[i] to the value at nums[j].
At the end, the length of the modified array is i + 1.
Complexity:
Time Complexity: O(n), where n is the length of the array (single traversal).
Space Complexity: O(1), as no extra space is used.
Usage
You can test this function like so:
python
Copy code
nums = [0,0,1,1,1,2,2,3,3,4]
new_length = removeDuplicates(nums)
print(new_length) # Output: 5
print(nums[:new_length]) # Output: [0, 1, 2, 3, 4] @TechWithMachines #datastructures #algorithm #leetcode #array #removeduplicatesfromsortedarray