Home
How to Remove Duplicates from Sorted Array in C/C++ (Constant Memory)?
Tags:, , , ,

How to Remove Duplicates from Sorted Array in C/C++ (Constant Memory)?

April 19, 2016 1 Comment algorithms, c / c++, leetcode online judge

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Submit your solution at: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Extra Space

If we allocate another array we can check each value for duplication with its previous value, the first pass fills the boolean array and the second re-fill the number array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<bool> flag(n, false);
        flag[0] = true;
        for (int i = 1; i < nums.size(); i ++) {
            flag[i] = nums[i] != nums[i - 1];
        }
        int r = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (flag[i]) {
                nums[r ++] = nums[i];
            }
        }
        return r;
    }
};
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        vector<bool> flag(n, false);
        flag[0] = true;
        for (int i = 1; i < nums.size(); i ++) {
            flag[i] = nums[i] != nums[i - 1];
        }
        int r = 0;
        for (int i = 0; i < nums.size(); i ++) {
            if (flag[i]) {
                nums[r ++] = nums[i];
            }
        }
        return r;
    }
};

This is O(n) time complexity and O(n) space complexity.

O(n^2)

When finding a duplicate, we can shift the numbers 1 position to the left, this moves the numbers in space, however O(n^2) is way too slow!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int r = 0;
        int n = nums.size();
        for (int i = 1; i < n; i ++) {
            if (nums[i] == nums[i - 1]) { // duplicate
                for (int k = i; k < n - 1; k ++) {
                    nums[k] = nums[k + 1]; // shifting 1 position left
                }
                --n; // shrink 1 number
            }
        }
        return n;
    }
};
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int r = 0;
        int n = nums.size();
        for (int i = 1; i < n; i ++) {
            if (nums[i] == nums[i - 1]) { // duplicate
                for (int k = i; k < n - 1; k ++) {
                    nums[k] = nums[k + 1]; // shifting 1 position left
                }
                --n; // shrink 1 number
            }
        }
        return n;
    }
};

O(n), O(1) space

This is the recommended as it does not use extra space and the time complexity is O(n). 

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int r = 0;
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[r] != nums[i]) {
                nums[++ r] = nums[i]; // copy-in next unique number
            }
        }
        return r + 1;
    }
};
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int r = 0;
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[r] != nums[i]) {
                nums[++ r] = nums[i]; // copy-in next unique number
            }
        }
        return r + 1;
    }
};

We use a index pointer to point to the last valid position in the sorted/handled array. If the next number is different than the last number, we increment the pointer and copy the value. This is all possible because the array is already sorted.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
475 words
Last Post: C++ Dynamic Programming Algorithm to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array
Next Post: How to Rotate Array in C/C++?

The Permanent URL is: How to Remove Duplicates from Sorted Array in C/C++ (Constant Memory)?

Related posts:

  1. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  2. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  3. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  4. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...
  5. How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)? Given a binary search tree and the lowest and highest boundaries as L and R,...
  6. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  7. A Simple Function to Perform Integer/Float Arithmetic Calculation via AWK The inbuilt BASH does not support floating point arithmetic calculations but we can easily declare...
  8. Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm) Given a singly linked list node, return its length. The linked list has fields next...

One Response

  1. ACMer

    This is a O(n).

    Reply

Leave a Reply