When working with arrays in programming, it's quite common to encounter scenarios where you need to remove duplicates while maintaining the original order of elements. In this blog post, we'll explore how to tackle this problem efficiently using Python.
Problem Statement
The problem at hand is to remove duplicates from a sorted integer array nums
in-place, such that each unique element appears only once. Additionally, we need to return the number of unique elements present in the modified array.
Approach
To solve this problem, we can utilize a two-pointer approach. We'll maintain two pointers, l
and r
, where l
represents the index for placing unique elements, and r
iterates through the array to check for duplicates.
Here's the step-by-step approach we'll follow:
- Initialize a pointer
l
to 1 (since the first element is always unique). - Iterate through the array with another pointer
r
starting from index 1. - Compare the element at index
r
with the element at indexr-1
. - If they are not equal, it means we've encountered a unique element.
- Move this unique element to the position pointed by
l
and incrementl
by 1. - Continue this process until we've iterated through the entire array.
- Return the value of
l
as it represents the count of unique elements.
Now, let's dive into the implementation.
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 1 # Initialize pointer l to 1
for r in range(1, len(nums)):
if nums[r] != nums[r-1]: # Check if current element is unique
nums[l] = nums[r] # Move unique element to position pointed by l
l += 1 # Increment l
return l # Return count of unique elements
Explanation
- We start by initializing
l
to 1, as the first element is always unique. - We iterate through the array starting from index 1 with pointer
r
. - At each iteration, we compare the current element (
nums[r]
) with the previous element (nums[r-1]
). - If they are not equal, it implies that we've encountered a unique element.
- We move this unique element to the position pointed by
l
. - Increment
l
to indicate the new position where the next unique element should be placed. - Finally, we return the value of
l
, which represents the count of unique elements in the modified array.
Conclusion
Removing duplicates from a sorted array in-place while maintaining the original order can be efficiently achieved using a two-pointer approach. By following the steps outlined above and implementing the provided Python solution, you can easily solve similar problems efficiently and effectively. Happy coding!
Checkout more Leetcode solutions.