Remove Duplicates from Sorted Array: A Comprehensive Guide
Written on
Chapter 1 Understanding the Problem
In this section, we will delve into the problem of removing duplicates from a sorted integer array, nums. The objective is to ensure that each unique element appears only once, while preserving the original order of the elements.
Given that the array is sorted in non-decreasing order, we need to modify the array in place, meaning we cannot use additional space for another array. Instead, our solution should place the unique elements at the front of the array. Formally, if k represents the number of unique elements, the first k elements of nums will hold the final output. The elements beyond the first k can be disregarded.
The function should return k after populating the first k slots of nums.
Here's a custom judge code snippet to test your solution:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: The function should return k = 2, with the first two elements of nums being 1 and 2.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: The function returns k = 5, and the first five elements of nums are 0, 1, 2, 3, and 4.
Constraints:
- 1 <= nums.length <= 30,000
- -100 <= nums[i] <= 100
- The array is sorted in non-decreasing order.
Chapter 2 Analysis
The challenge becomes simpler if we are allowed to use extra space, as we could utilize a map to store unique elements and their frequencies. However, since we must operate in place, we need a more intricate approach.
Approach 1: Two Indexes Method
To tackle this problem effectively, we must consider that the array is sorted. This means that all duplicate values will be adjacent to each other. We will keep track of the count of unique elements with k.
To fill the first k elements with unique values while modifying the array in place, we will implement a two-index approach:
- Initialize two indices: insertIndex and i, both starting at 0.
- Check for uniqueness: Compare the current element with the previous one. If they differ, we will place the current element at the insertIndex position and increment insertIndex.
- Continue until the end: Increment i until it reaches the end of the array.
The algorithm can be summarized as follows:
- Start both indices at 0.
- If nums[i] is different from nums[i-1], assign nums[insertIndex] = nums[i] and increment insertIndex.
- Continue until the end of the array.
Here's a visual representation of the process:
Python Solution
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
size = len(nums)
insertIndex = 1
for i in range(1, size):
if nums[i - 1] != nums[i]:
nums[insertIndex] = nums[i]
insertIndex += 1
return insertIndex
C++ Solution
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int insertIndex = 1;
for(int i = 1; i < nums.size(); i++){
if(nums[i - 1] != nums[i]) {
nums[insertIndex] = nums[i];
insertIndex++;
}
}
return insertIndex;
}
};
Java Solution
class Solution {
public int removeDuplicates(int[] nums) {
int insertIndex = 1;
for(int i = 1; i < nums.length; i++){
if(nums[i - 1] != nums[i]) {
nums[insertIndex] = nums[i];
insertIndex++;
}
}
return insertIndex;
}
}
Complexity Analysis
- Time Complexity: O(N)
- Space Complexity: O(1)
Chapter 3 Additional Resources
For further insights into algorithmic interview questions, check out the following videos:
This video titled "Top Algorithm Interview Questions Fully Explained" will provide you with a detailed understanding of various algorithm-related queries.
The second video, "Remove Duplicates from Sorted Array | Leetcode 26 | Top 150 interview question series," focuses specifically on this topic, offering examples and explanations that complement our discussion.
Stay tuned for more engaging interview questions and coding challenges. I'm a senior software engineer at MANNG, and I invite you to follow my journey for more interesting insights into the tech world.