26. Remove Duplicates from Sorted Array
Problem Description
The problem presents an integer array called nums
that is sorted in non-decreasing order. The goal is to remove duplicates from nums
in a way that each unique element appears only once while maintaining the relative order of elements. This task must be done in-place, which means that we should not allocate extra space for another array, and we have to modify the original array instead.
Once duplicates are removed, we are required to return the new length of the array, which represents the number of unique elements. The first part of the array up to this new length should contain all unique elements in their original order, and whatever follows after doesn't matter.
To adhere to the problem's constraints, the final arrangement of the array and the value of k
are checked against the expected result using the provided custom judge implementation. In simple terms, after calling the solution function, the array nums
should have its first k
elements without duplicates and k
should equal the expected number of unique elements.
Intuition
To arrive at the solution, we realize that since the array is already sorted, duplicates will be adjacent to each other. Hence, we can simply iterate through the array and compare each element with the previous one (except for the first element) to identify duplicates.
Our intuition should tell us that we need two pointers here: one for iterating over the array (x
in this case) and another to keep track of the location in nums
where the next unique element should be placed (k
).
Starting with k
at 0, we move through the array with x
and when x
is not equal to nums[k - 1]
(which would mean x
is not a duplicate), we place x
at nums[k]
and increment k
. This works because when x
is a duplicate of nums[k - 1]
, we simply skip it by not incrementing k
, hence overwriting the duplicates in subsequent steps.
The process continues to the end of the array, ensuring that all unique elements are moved to the front of the array, and k
represents the number of unique elements. By the end of the iteration, we return k
as the result.
Learn more about Two Pointers patterns.
Solution Approach
The solution to this problem uses a technique commonly known as the two-pointer approach. This approach is often applied in array manipulation problems, especially when we need to modify the array in-place to satisfy certain constraints.
Here's how the two-pointer technique is applied step by step:
Step 1: Initialize Pointer k
A pointer k
is initialized to 0. This pointer is used to track the position where the next unique element should be placed in the array.
Step 2: Iterate Through the Array
We iterate over each element x
in the array nums
. During iteration, k
is used as a slow-runner pointer, while the loop index (implicitly represented by the iteration over x
) acts as a fast-runner pointer.
Step 3: Identify Unique Elements
We only want to act when we come across a unique element. A unique element in this sorted array is identified by checking if it is different than the element at the position just before the current k
. This is represented by the condition x != nums[k - 1]
.
Step 4: Place Unique Elements and Increment Pointer k
When a unique element is found, we copy it to nums[k]
and then increment k
. This effectively shifts the unique elements to the front of the array and steps over any duplicates.
The first element is a special case because there is no nums[k - 1]
when k
is 0, so it's always considered unique, and we start k
at 0 by default.
Step 5: Handle Duplicates
When a duplicate element (which is not unique) is encountered, the body of the if
condition does not execute, which means that k
is not incremented. This implies that the duplicate value will be overwritten in the next iteration when a new unique element is encountered.
Step 6: Return the Count of Unique Elements
After the iteration is completed, k
holds the total count of unique elements, as it was incremented only when encountering a unique element. We return k
at the end.
Here is how the implementation looks in Python:
1class Solution:
2 def removeDuplicates(self, nums: List[int]) -> int:
3 k = 0
4 for x in nums:
5 if k == 0 or x != nums[k - 1]:
6 nums[k] = x
7 k += 1
8 return k
In this code, the if k == 0
check allows us to handle the first element correctly, and the subsequent x != nums[k - 1]
checks help in identifying if the current element is different from the element that was last identified as unique.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following sorted integer array nums
:
1nums = [1, 1, 2, 2, 3]
Our goal is to remove duplicates using the algorithm described.
Initial Setup
We initialize k
to 0
. At this point, the array is unchanged.
Iteration 1
Element at index 0
is 1
. Since k
is 0
, the first element is considered unique by default. We assign nums[k]
to 1
and increment k
to 1
.
Updated array state:
1nums = [1, 1, 2, 2, 3] 2k = 1
Iteration 2
Element at index 1
is also 1
. This is a duplicate of nums[k - 1]
. We do not increment k
.
Updated array state (no changes, duplicate ignored):
1nums = [1, 1, 2, 2, 3] 2k = 1
Iteration 3
Element at index 2
is 2
. Now, nums[k - 1]
is 1
, so 2
is unique. We assign nums[k]
to 2
and increment k
to 2
.
Updated array state:
1nums = [1, 2, 2, 2, 3] 2k = 2
Iteration 4
Element at index 3
is 2
. This is a duplicate of nums[k - 1]
. Again, k
is not incremented.
Updated array state (no changes, duplicate ignored):
1nums = [1, 2, 2, 2, 3] 2k = 2
Iteration 5
Element at index 4
is 3
. Now, nums[k - 1]
is 2
, so 3
is unique. We assign nums[k]
to 3
and increment k
to 3
.
Updated array state:
1nums = [1, 2, 3, 2, 3] 2k = 3
Conclusion
We've finished iterating over nums
. The first k
(3) elements [1, 2, 3] are the unique numbers from the original array. The rest of the array doesn't matter for this problem.
We return k
, which is 3
, indicating the number of unique elements in the modified array.
The final state of nums
is:
1nums = [1, 2, 3, 2, 3]
And the returned value is 3
.
Solution Implementation
1class Solution:
2 def removeDuplicates(self, nums: List[int]) -> int:
3 # Initialize the array position marker k to 0.
4 # This will keep track of the position in the array
5 # where the next unique element should be placed.
6 k = 0
7
8 # Loop through each number in the nums array.
9 for x in nums:
10 # Check if k is 0, which means we're at the start of the array
11 # or if the current number is not equal to the last unique number we've seen.
12 # The condition k == 0 is true for the first element,
13 # so we store it as the first unique element.
14 if k == 0 or x != nums[k - 1]:
15 # Place the current unique element at the k-th position in the array.
16 nums[k] = x
17 # Increment k to indicate that the next unique element should be placed in the next position.
18 k += 1
19
20 # Return the length of the array that contains all unique elements,
21 # which is also the new length of the array without duplicates.
22 return k
23
1class Solution {
2 // Method to remove duplicates from sorted array
3 // and return the length of the array after duplicates have been removed.
4 public int removeDuplicates(int[] nums) {
5 // Initialize the count for unique elements
6 int uniqueCount = 0;
7
8 // Iterate over each element in the array
9 for (int currentNum : nums) {
10 // If it's the first element or is not equal to the previous element
11 // (which means it's not a duplicate)
12 if (uniqueCount == 0 || currentNum != nums[uniqueCount - 1]) {
13 // Assign the current number to the next unique position in the array
14 nums[uniqueCount++] = currentNum;
15 }
16 }
17
18 // Return the count of unique elements, which is also the new length of the array
19 return uniqueCount;
20 }
21}
22
1#include <vector> // Required to use the std::vector container
2
3// Solution class encapsulates the method to remove duplicates from an array.
4class Solution {
5public:
6 // Method to remove duplicates from a sorted vector in-place.
7 // @param nums is a reference to a vector of integers.
8 // @return The new length of the vector after duplicates have been removed.
9 int removeDuplicates(std::vector<int>& nums) {
10 // The std::unique function returns an iterator to the element that follows the last element
11 // not removed. The range between this iterator and the end of the vector contains all the
12 // elements that need to be removed.
13 auto newEnd = std::unique(nums.begin(), nums.end());
14
15 // Erase the non-unique elements from the vector using the erase function.
16 // This mutates the vector and adjusts its size accordingly.
17 nums.erase(newEnd, nums.end());
18
19 // Return the new size of the vector after removing duplicates.
20 return nums.size();
21 }
22};
23
1/**
2 * Removes all duplicates from a sorted array of numbers.
3 * Duplicates are removed in-place and the function returns
4 * the new length of the array after duplicates have been removed.
5 *
6 * @param {number[]} nums - A sorted array of numbers from which to remove duplicates.
7 * @return {number} The new length of the array after duplicate removal.
8 */
9function removeDuplicates(nums: number[]): number {
10 // Initialize the index for the next unique element.
11 let nextUniqueIndex: number = 0;
12
13 // Iterate through the array of numbers.
14 for (const currentElement of nums) {
15 // If we're at the start of the array or the current element is not
16 // the same as the last unique element, we treat it as unique.
17 if (nextUniqueIndex === 0 || currentElement !== nums[nextUniqueIndex - 1]) {
18 // Store the current element at the next unique position.
19 nums[nextUniqueIndex] = currentElement;
20 // Increment the index for the next unique element.
21 nextUniqueIndex++;
22 }
23 // If the current element is the same as the last unique element,
24 // the loop continues without doing anything, effectively skipping duplicates.
25 }
26
27 // Return the new length of the array after all duplicates have been removed.
28 // This length is equivalent to the next unique element's index.
29 return nextUniqueIndex;
30}
31
Time and Space Complexity
Time Complexity:
The given algorithm iterates through each element of the list exactly once. During each iteration, the algorithm performs a constant number of operations: a comparison, an assignment (when necessary), and an increment of the k
counter. The time complexity is therefore linear relative to the length of the input list nums
. If n
represents the number of elements in nums
, the time complexity can be expressed as O(n)
.
Space Complexity:
The algorithm modifies the list nums
in place and does not require any additional space that grows with the size of the input, except for the counter variable k
. Therefore, the auxiliary space requirement is constant, and the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first