80. Remove Duplicates from Sorted Array II
Problem Description
Imagine you have a list of numbers that are sorted in ascending order, but some numbers appear more than once. Your task is to modify this list so that each unique number appears no more than twice. However, the challenge is to do this without using any additional space and to modify the original list directlyāthat means you can't create a new list to hold the result. You need to ensure the final list still remains sorted.
For example, if your list is [1,1,1,2,2,3,3,3,3]
, your goal is to change it to something like [1,1,2,2,3,3,__,__,__]
(with the underscores representing spaces you don't care about).
Ultimately, you'll return the length of the modified list (in the example above, it would be 6 since there are six numbers in the list after duplicates beyond the second instance are removed).
Intuition
The solution uses a two-pointer approach that exploits the fact that the input array is already sorted. The essence of the approach is to iterate over the array and make sure that we're copying over each unique element at most twice to the 'front' part of the array.
We use a variable k
as a pointer to keep track of the 'ęęꮵ' (or the valid segment) of the list ā the portion that contains no more than two instances of any number. When we find a number that should be part of the valid segment, we copy it to the position indicated by k
and increment k
.
As we go through the list, for each new element we check:
- If
k
is less than 2, which means we're still filling up the first two slots, we can safely add the number without any checks. - If the current number is not the same as the element two places before it in our 'ęęꮵ' (valid segment of the list), we know that we haven't yet seen it twice, so we copy it to the current
k
position.
This way, once we've gone through the entire list, k
points just past the last element of the desired valid segment. We don't care what's beyond it, and we return k
as the new length of the non-duplicated (up to twice) list.
Learn more about Two Pointers patterns.
Solution Approach
The solution provided employs a simple algorithm with no additional data structures, adhering to an in-place modification constraint which is necessary for this problem. We use the two-pointer technique, but with just one variable k
as the slow-runner pointer, while the for x in nums
loop acts as the fast-runner pointer.
Here's a step-by-step explanation of the implementation:
-
We initialize the pointer
k
to zero. This will keep track of the position in the array where we will place the next unique element that we want to keep, which should appear at most twice. -
We iterate over each number
x
innums
using afor
loop. -
For each number, we have two conditions to check:
- If
k < 2
: This means we are at the beginning ofnums
, and since we can have at least two of the same element, we don't need to check for duplicates yet. - If
x != nums[k - 2]
: This is checked whenk
is greater than or equal to 2. Since the array is sorted, if the current numberx
is different from the two places before the currentk
index, it meansx
is different from at least the last two numbers in our "valid segment", so we can safely includex
in our result.
- If
-
If either condition is true, we assign the current number
x
to thek
th position in the array, thereby ensuring it is part of the final array, and incrementk
. -
After the loop finishes,
k
is now the length of the array with no duplicates (allowing up to two instances of the same number). We returnk
as the result.
The key to this algorithm is understanding that since the array is sorted, duplicates are always adjacent. By checking two steps back, we ensure that we only keep at most two instances of any element. Furthermore, using only the variable k
to manage the valid part of the array ensures that we comply with the O(1) extra space constraint of the problem, as we're just rearranging the elements and not using any extra space.
This is the heart of the solutionāthe algorithm relies solely on the sorted nature of the array and the clever use of a single index to keep track of our "valid segment".
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 illustrate the solution approach with a small example. Suppose our input array is:
nums = [1, 1, 1, 2, 3, 3, 4]
According to the problem description, we want to modify the array so that no number appears more than twice and we want to do this in place. Here's how we apply the two-pointer technique with the variable k
:
-
We initialize
k
to zero. -
Start iterating over each number in
nums
.a.
x = 1
,k = 0
(k < 2 is True). Place1
atnums[0]
, incrementk
to 1.b.
x = 1
,k = 1
(k < 2 is True). Place1
atnums[1]
, incrementk
to 2.c.
x = 1
,k = 2
(k < 2 is False, butx != nums[k - 2]
is False sincenums[0]
is 1). We skip this step.d.
x = 2
,k = 2
(Sincex
is different fromnums[k - 2]
=> 2 !=nums[0]
). Place2
atnums[2]
, incrementk
to 3.e.
x = 3
,k = 3
(Sincex
is different fromnums[k - 2]
=> 3 !=nums[1]
). Place3
atnums[3]
, incrementk
to 4.f.
x = 3
,k = 4
(Sincex
is different fromnums[k - 2]
=> 3 !=nums[2]
). Place3
atnums[4]
, incrementk
to 5.g.
x = 4
,k = 5
(Sincex
is different fromnums[k - 2]
=> 4 !=nums[3]
). Place4
atnums[5]
, incrementk
to 6. -
By the end of the iteration, our array looks like this:
nums = [1, 1, 2, 3, 3, 4, __]
Here, __
represents the space we don't care about. The array nums
now contains each unique number no more than twice, in sorted order, and k
(which is 6) indicates the length of the modified array that we are concerned with. Therefore, we return k
as the answer which is 6
in this case.
Solution Implementation
1from typing import List
2
3class Solution:
4 def removeDuplicates(self, nums: List[int]) -> int:
5 # Initialize the count of unique elements
6 unique_count = 0
7
8 # Iterate over each number in the input list
9 for num in nums:
10 # Check if the current number is different from the number
11 # at position unique_count - 2.
12 # This is to allow a maximum of two duplicates.
13 if unique_count < 2 or num != nums[unique_count - 2]:
14 # If condition met, copy the current number to the next position in the array.
15 nums[unique_count] = num
16 # Increment the count of unique elements.
17 unique_count += 1
18
19 # Return the length of the array containing no more than two duplicates of each element.
20 return unique_count
21
1class Solution {
2 public int removeDuplicates(int[] nums) {
3 // 'k' is the index for placing the next unique element
4 // or the second occurrence of an existing element
5 int index = 0;
6
7 // Iterate over each element in the array
8 for (int num : nums) {
9 // If the current position is less than 2 (i.e., we are at the start of the array)
10 // or if the current element is different than the element two positions behind
11 // then consider it for inclusion in the array
12 if (index < 2 || num != nums[index - 2]) {
13 // Place the current element at the 'index' position and increment 'index'
14 nums[index] = num;
15 index++;
16 }
17 }
18
19 // The 'index' represents the length of the array without duplicates
20 // allowing up to two occurrences
21 return index;
22 }
23}
24
1#include <vector> // Include vector header for using the vector container
2
3// Solution class containing the method to remove duplicates
4class Solution {
5public:
6 // Method to remove duplicates from sorted array allowing at most two occurrences of each element
7 int removeDuplicates(vector<int>& nums) {
8 // Initialize the counter for the new length of the array
9 int newLength = 0;
10
11 // Iterate through each number in the input vector
12 for (int num : nums) {
13 // Check if we have seen less than 2 occurrences or if the current number
14 // is not a duplicate of the number at newLength - 2 position
15 if (newLength < 2 || num != nums[newLength - 2]) {
16 // If the condition is true, copy the current number to the new position
17 // and increase the length counter
18 nums[newLength++] = num;
19 }
20 }
21
22 // Return the new length of the array after duplicates are removed
23 return newLength;
24 }
25};
26
1function removeDuplicates(nums: number[]): number {
2 // Initialize the count, k, to be the index at which we insert the next unique element.
3 let count = 0;
4
5 // Iterate through each number in the given array.
6 for (const current of nums) {
7 // If the count is less than 2 or the current number is not equal to
8 // the number two places before in the array, it is not a duplicate (or it's
9 // the second occurrence of a number that is allowed twice), so we add it to the array.
10 if (count < 2 || current !== nums[count - 2]) {
11 nums[count] = current;
12 count++; // Increment the count since we've added a unique number.
13 }
14 }
15
16 // Return the new length of the array after duplicates have been removed.
17 // Elements after the returned length are considered irrelevant.
18 return count;
19}
20
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
, where n
is the number of elements in the input list nums
. This is because the code consists of a single loop that goes through all elements of the list exactly once.
Space Complexity
The space complexity of the code is O(1)
. No additional space is required that is dependent on the input size. The variable k
is used to keep track of the position in the array while overwriting duplicates, but this does not scale with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
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
Want a Structured Path to Master System Design Too? Donāt Miss This!