English flagEnglish  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove all duplicates in-place so that each unique element appears only once. Return the number of unique elements in the array.

If the number of unique elements be k, then,

Change the array nums such that the first k elements of nums contain the unique values in the order that they were present originally.
The remaining elements, as well as the size of the array does not matter in terms of correctness.

An array sorted in non-decreasing order is an array where every element to the right of an element in either equal to or greater in value than that element.

LeetCode:

Constraints

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Examples

Example 1:

Input: arr [1, 2, 5, 5, 6, 6, 7]
Output: arr [1, 2, 5, 6, 7, _, _]

Exaplanation: There are five distinct elements in array and the elements
marked as _ can have any value.
Example 2:

Input: arr [-5, -1, 0, 0, 1, 2]
Output: arr [-5, -1, 0, 1, 2, _]

Example: There are five distinct elements in array and the elements
marked as _ can have any value.

Different Approaches

1️⃣ Brute Force Approach (Using set)

std::set is an effective approach for removing duplicates from a sorted array. set only stores unique elements. Copy all the elements back from the set to the original array.

Algorithm:

  1. Initialize an empty Set.
  2. iterate through each element of the array and keep pushing in the set.
  3. Create an empty array.
  4. Iterate through unique element in the set and keep putting in the original array.

Code:

#include<bits/stdc++.h>

using namespace std;

int removeDuplicates(int arr[], int n) {
  // Use a set to store unique elements
  set <int> set;
  
  // Insert elements from arr[] into the set
  for (int i = 0; i < n; i++) {
    set.insert(arr[i]);
  }
  
  // Get the number of unique elements
  int k = set.size();
  int j = 0;
  
  // Copy unique elements from set to nums
  for (int x: set) {
    arr[j++] = x;
  }
  
  // Return the number of unique elements.
  return k;
}
int main() {
  int arr[] = {1,1,2,2,2,3,3};
  int n = sizeof(arr)/sizeof(arr[0]);
  int k = removeDuplicates(arr, n);
  cout << "The array after removing duplicate elements is " << endl;
  for (int i = 0; i < k; i++) {
    cout << arr[i] << " ";
  }
}

Complexity Analysis:

  • Time Complexity:O(n log n)
    • Inserting each element into the set takes O(log n)time, and there are n elements in the array.
    • Iterating through the set takes O(n) time.
    • Thus, the overall time complexity is dominated by the insertion operation, resulting in O(n log n), if we ignore the dominated operation, it would be O(n log n) + O(n)
  • Space Complexity: O(n)
    • Additional space is required for the set and the vector.
    • The size of the set could be at most n , where n is the number of unique elements in the array.
    • Therefore, the space complexity is O(n).

2️⃣ Two Pointers Approach

Algorithm:

  1. Initialization:
    1. We start by initializing two pointers, i, and j, both pointing to the beginning of the array.
    2. Pointer i will keep track of the index where unique elements will be placed.
    3. Pointer j will be used to iterate through the array.
  2. Iterating through the array:
    1. We begin iterating through the array with the pointer j, starting from the second element.
    2. At each step, we compare the element at index j with the element at index i.
    3. If the elements are different, it means we have encountered a new unique element.
    4. In this case, we copy the unique element at index j to the position i + 1 in the array.
    5. We then increment i to point to the next position where the next unique element will be placed.
  3. Unique Elements:
    1.  As we iterate through the array, each unique element encountered is copied to the position pointed by i.
    2. After the iteration completes, all unique elements are compactly placed in the beginning of the array, from index 0 to i.
  4. Removing Duplicates:
    1. If there are duplicate elements in the array, they will be overwritten as we copy unique elements.
  5. Returning the Length:
    1. After the iteration, i points to the last unique element in the array.
    2. We return i + 1, which represents the length of the array containing only unique elements.

Dry Run:

Initialization:

      +-----+-----+-----+-----+-----+------+-----+
arr : |  0  |  0  |  1  |  1  |  1  |  2   |  2  |
      +-----+-----+-----+-----+-----+------+-----+
         0     1     2     3     4     5      6
         i     j
First Iteration:
      --------------------------------------------
arr : |  0  |  0  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
         i     j
   arr[i] != arr[j]
   0 != 0
   false

hence, increment j by 1

      --------------------------------------------
arr : |  0  |  0  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
         i           j
Second Iteration:
      --------------------------------------------
arr : |  0  |  0  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
         i           j

   arr[i] != arr[j]
   0 != 1
   true

First Increment i, which would point to index 1, arr[1] = 0
set arr[i] = arr[j]
Increment j by 1

      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i           j
Third Iteration:
      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i           j

   arr[i] != arr[j]
   1 != 1
   false

Increment j by 1

      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i                 j
Fourth Iteration:
      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i                 j

   arr[i] != arr[j]
   1 != 1
   false

Increment j by 1

      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i                       j
Fifth Iteration:
      --------------------------------------------
arr : |  0  |  1  |  1  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
               i                       j

   arr[i] != arr[j]
   1 != 2
   true

First Increment i, which would point to index 2, arr[2] = 1
set arr[i] = arr[j]
arr[2] = arr[5]
arr[2] = 2 

Increment j by 1

      --------------------------------------------
arr : |  0  |  1  |  2  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
                     i                        j
Sixth Iteration:
      --------------------------------------------
arr : |  0  |  1  |  2  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
                     i                        j

   arr[i] != arr[j]
   2 != 2
   false


Increment j by 1

      --------------------------------------------
arr : |  0  |  1  |  2  |  1  |  1  |  2   |  2  |
      --------------------------------------------
         0     1     2     3     4     5      6
                     i                               j

j becomes out of bounds so break the loop,
and return i + 1 = number of unique elements.

Code:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // Edge case: empty array
        if (nums.empty()) return 0;

        // 'uniqueIndex' keeps track of the last index where a unique element was placed
        int uniqueIndex = 0;

        // Start from the second element and compare with the last unique one
        for (int i = 1; i < nums.size(); i++) {

            // If current element is not equal to the last unique element
            if (nums[i] != nums[uniqueIndex]) {

                // Move the unique index forward
                uniqueIndex++;

                // Place the new unique element at the new position
                nums[uniqueIndex] = nums[i];
            }
        }

        // Number of unique elements is index + 1
        return uniqueIndex + 1;
    }
};

Complexity Analysis:

  • Time Complexity:O(N), for single traversal of the array, where N is the size of the array.
  • Space Complexity:O(1), not using any extra space.
Your experience on this site will be improved by allowing cookies Cookie Policy