Problem Statement
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
- Change the array
numssuch that the firstkelements ofnumscontain the unique elements in the order they were present innumsinitially. The remaining elements ofnumsare not important as well as the size ofnums. - Return
k.
LeetCode Link
Remove Duplicates from Sorted Array
Constraints
1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.Examples
Example 1:
Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).Different Approaches
1️⃣ Using Unordered Set (Extra Space)
Approach:
The algorithm for removing duplicate values from an array involves iterating through each element and keeping track of unique values encountered so far. Here's a step-by-step breakdown of the algorithm:
- Initialize an empty set or hash table to store unique values.
- Iterate through the array.
- For each element, check if it is already present in the set.
a. If not present, add it to the set and include it in the modified array.
b. If already present, skip the element. - The modified array now contains only unique values.
Dry Run:
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
set = | |
| (empty) |
+---------+
+-----+
result = | |
+-----+Iterate over the nums with i from 0 to n - 1
set = | |
| (empty) |
+---------+
+-----+
result = | |
+-----+
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
i = 0
Does nums[i] exist in the set.
nums[0] = 1, it does not exist
So, add to the set and result as well.set = | |
| 1 |
+-----+
+-----+
result = | 1 |
+-----+
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
i = 1
Does nums[i] exist in the set.
nums[1] = 1, it does exist
So, do nothingset = | |
| 1 |
+-----+
+-----+
result = | 1 |
+-----+
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
i = 2
Does nums[i] exist in the set.
nums[2] = 2, it does not exist
So, add 2 in both set and result array.set = | |
| 2 |
+-----+
| 1 |
+-----+
+-----+-----+
result = | 1 | 2 |
+-----+-----+
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
i = 3
Does nums[i] exist in the set.
nums[3] = 2, it does exist
So, do nothingset = | |
| 2 |
+-----+
| 1 |
+-----+
+-----+-----+
result = | 1 | 2 |
+-----+-----+
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
As i exceeds the array boundary (out of bounds)
We stop here and return the result array which contains the
unique elements.Code:
#include <iostream>
#include <unordered_set>
#include <vector>
// Function to remove duplicate values from an array
std::vector<int> removeDuplicates(const std::vector<int>& inputArray) {
// Create an unordered_set to store unique values
std::unordered_set<int> uniqueSet;
// Create a vector to store the modified array without duplicates
std::vector<int> result;
// Iterate through each element in the input array
for (const auto& element : inputArray) {
// Check if the element is not present in the set
if (uniqueSet.find(element) == uniqueSet.end()) {
// If not present, add it to the set
uniqueSet.insert(element);
// Also include it in the modified array
result.push_back(element);
}
}
// Return the modified array without duplicate values
return result;
}
// Main function
int main() {
// Example usage: an array with duplicate values
std::vector<int> inputArray = {1, 2, 3, 2, 4, 5, 6, 1};
// Call the removeDuplicates function to get the modified array
std::vector<int> modifiedArray = removeDuplicates(inputArray);
// Output the modified array
std::cout << "Modified Array: ";
for (const auto& element : modifiedArray) {
std::cout << element << " ";
}
// Return 0 to indicate successful execution
return 0;
}
// Output
Modified Array: 1 2 3 4 5 6 Explanation:
Function removeDuplicates:
- The
removeDuplicatesfunction take a constant reference to an input array (inputArray). - It initializes an unordered set (
uniqueSet) to store unique values encountered during the iteration. - Another vector (
result) is created to store the modified array without duplicate values. - The function iterates through each element in the input array using a range-based for loop.
- For each element, it checks whether the element is present in the set (
uniqueSet) usingfind. - If the element is not present, it means it's unique.
- It adds the element to the set and also includes it in the modified array (
result). - In the
mainfunction, an example array with duplicate values (inputArray) is created and theremoveDuplicatesfunction is called to obtain the modified array without duplicates (modifiedArray).
Complexity Analysis:
- Time Complexity: The time complexity of this algorithm is
O(N), whereNis the number of elements in the input array. This is because each element is visited only once. - Space Complexity: The space complexity is also
O(N)as the unordered set may store all unique elements from the array. In the worst case, where all elements are unique, the set's size would be equal to the array size.
2️⃣ Frequency Map
Intuition:
A frequency map tells how many times each element occurs; we can keep only one of each.
Approach:
- Use
unordered_map<int, int>to store frequency. - Keep only unique elements.
Dry Run:
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
map = | |
| (empty) |
+---------+
+-----+
result = | |
+-----+Iterate over the nums array from 0 to n-1
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
map = | |
| (empty) | <element, frquency>
+---------+
+-----+
result = | |
+-----+
i = 0
Does frequency of nums[i] is 0 in map
Yes it is
So add it to the map as well as in the result vector. +-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
map = | |
| (1, 1) | <element, frquency>
+---------+
+-----+
result = | 1 |
+-----+
i = 1
Does frequency of nums[i] is 0 in map
No it has 1 frequency
So do nothing +-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
map = | |
| (1, 1) | <element, frquency>
+---------+
+-----+
result = | 1 |
+-----+
i = 2
Does frequency of nums[i] is 0 in map
Yes 2 has 0 frequency
So add 2 in the map as well as in the result. +-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
map = | (2, 1) |
| (1, 1) | <element, frquency>
+---------+
+-----+-----+
result = | 1 | 2 |
+-----+-----+
i = 3
Does frequency of nums[i] is 0 in map
No, 2 has 1 frequency
So do nothing. +-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
map = | (2, 1) |
| (1, 1) | <element, frquency>
+---------+
+-----+-----+
result = | 1 | 2 |
+-----+-----+
i has exceeded the array bounds, so return the result array, as
it would contain the unique elements.Code:
vector<int> removeDuplicates(vector<int>& nums) {
// Step 1: Create a hash map to store the frequency of each number
unordered_map<int, int> freq;
// Step 2: Create a new vector to store the result (unique elements)
vector<int> result;
// Step 3: Loop through each number in the input array
for (int num : nums) {
// Step 4: If this number hasn't been seen before (frequency is 0)
if (freq[num]++ == 0) {
// Step 5: Add it to the result vector
result.push_back(num);
}
// If it's already been seen, do nothing (skip duplicates)
}
// Step 6: Return the result vector containing only unique elements
return result;
}
Complexity Analysis:
- Time Complexity:
O(n)- As we are traversing the array once.
- Space Complexity:
O(n)- In the worst case, when all elements are unique then map stores all the elements.
3️⃣ Two Pointers (In-Place) (Optimal)
Intuition:
Because the array is sorted, duplicates are next to each other. We can shift unique elements towards the front using two pointers.
Note: If unsorted array is given, then first sort the array and do the same process.
Approach:
- Initialize
i = 0(last unique element index) - Iterate with
jfrom1to end:- If
nums[j] != nums[i], incrementiand copynums[j]tonums[i]
- If
🔍 Dry Run:
Initialization:
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
set i = 0Iterate from j = 1 to n - 1 in nums array
i = 0
j = 1 (loop)
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[i] != nums[j]
nums[0] != nums[1]
1 != 1
False
Do nothing, i will reamin same and j will proceed to
next iteration.i = 0
j = 2 (loop)
+-----+-----+-----+-----+
nums = | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[i] != nums[j]
nums[0] != nums[2]
1 != 2
True
Increment i (i becomes 1)
Set nums[i] = nums[j]
nums[1] = nums[2]
Over to the next iteration of the loop.i = 1
j = 3 (loop)
+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
Check if nums[i] != nums[j]
nums[1] != nums[3]
2 != 2
False
Do nothing
Over to the next iteration of the loop.i = 1
j = 4 (loop) (out of bounds)
+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^ ^
| |
i j
As the j exceeds the array bounds, the loop will terminate.
till i the array contains the unique elements.
As our problem demands us to return the count,
just return i + 1, as it contains the count of
unique elements.Final State:
+-----+-----+-----+-----+
nums = | 1 | 2 | 2 | 2 |
+-----+-----+-----+-----+
0 1 2 3
^
|
i
Return: i + 1 = 1 + 1 = 2
Unique elements = [1, 2]Code:
int removeDuplicates(vector<int>& nums) {
// Step 1: If the input array is empty, return 0 (no elements to process)
if (nums.empty()) return 0;
// Step 2: Initialize a pointer `i` to keep track of the position
// where the next unique element should be placed
int i = 0;
// Step 3: Start a loop from the second element (index 1) to the end of the array
for (int j = 1; j < nums.size(); ++j) {
// Step 4: If the current element is different from the last unique element
if (nums[j] != nums[i]) {
// Step 5: Move the pointer `i` forward to the next position
++i;
// Step 6: Copy the unique element to the new position
nums[i] = nums[j];
}
// If nums[j] == nums[i], it's a duplicate, so skip it
}
// Step 7: Return the count of unique elements, which is `i + 1`
return i + 1;
}
Complexity Analysis:
- Time Complexity:
O(n)- As we are traversing the array once
- Space Complexity:
O(1)- No extra space is used.