Reference: LeetCode
Difficulty: Easy

Problem

Given a sorted array nums, 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 by modifying the input array in-place with $O(1)$ extra memory.

Example: 

1
2
3
4
5
6
7
Given nums = [1, 1, 2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

Given nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what you leave beyond the returned length.

Analysis

Brute-Force

The code is adapted from EPI 5.5 using List class. Basically, we just remove duplicates, but if we use array we need to implement the remove() code by ourselves.

Note:

  • remove() takes $O(N)$ time.
  • Use equals rather than ==.
  • A.size() is dynamic, which means it is always changing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int deleteDuplicates(List<Integer> A) {
  //  0  1  2  3  4  5
  //  1  2  2  3  3  4
  //  i  i+1
  int i = 0;
  while (i < A.size() - 1) { // dynamic size, skip the last
    if (A.get(i).equals(A.get(i + 1))) { // equal
      A.remove(i + 1);
    } else { // not equal
      ++i; // move forward
    }
  }
  return A.size();
}

Time: $O(N^2)$
Space: $O(1)$

Moving to Subarray

Use an index idx to store the processed element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// case: [1 1 2 2]
// case: [1 1 2 3]
public int removeDuplicates(int[] nums) {
  // assume `nums` is not null
  int n = nums.length;
  int idx = 0;
  for (int i = 0; i < n; ++i) {
    if (i < n - 1 && nums[i] == nums[i + 1]) {
      continue;
    } else { // the last element always falls into this branch (try the two test cases above)
      nums[idx++] = nums[i];
    }
  }
  return idx;
}

Time: $O(N)$
Space: $O(1)$

Two Pointers

This is a solution in LeetCode, but I think it is not clear. Also, using this solution needs processing corner case (n == 0).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 0  1  2  3  4  5  6
// 1  2  2  3  3  4  5
// i  j
//   i/j
//    i  j
//    i     j
//       i  j
//       i(3)  j(3)
//       i(3)     j
//          i(4)     j
//             i(5)     j
public int removeDuplicates(int[] nums) {
  int n = nums.length;
  if (n == 0) {
    return 0;
  }
  int i = 0;
  for (int j = 1; j < n; ++j) { // as long as nums[i] == nums[j], increment j to skip dups
    if (nums[i] != nums[j]) { // when nums[i] != nums[j], dups have ended.
      ++i; // move to the next new position
      nums[i] = nums[j];
    }
  }
  return i + 1;
}

Variants

Variant 1:

Implement a function which takes an input an array and a key, and updates the array so that all occurrences of the input key have been removed and the remaining elements have been shifted left to fill the emptied indices. Return the number of remaining elements. There are no requirements as to the values stored beyond the last element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Testing
public static void main(String[] args) {
  List<Integer> L = new ArrayList<>();
  int[] nums = new int[] { 3, 4, 2, 1, 1, 9, 1, 2 };
  for (int val : nums) L.add(val); // result: [3, 4, 2, 9, 2]
  System.out.println("count: " + removeOccurrence(L, 1));
  System.out.println("List: " + L);
}

// O(N)
public static int removeOccurrence(List<Integer> A, int key) {
  int i = 0, idx = 0;
  while (i < A.size()) {
    if (A.get(i).equals(key) == false) { // equal to the occurrence
      A.set(idx++, A.get(i));
    }
    ++i;
  }
  return idx;
}

Variant 2:

Write a program which takes as input a sorted array $A$ of integers and a positive integer $m$, and updates $A$ so that if $x$ appears $m$ times in $A$ it appears exactly min(2, m) times in $A$. The update to $A$ should be performed in one pass, and no additional storage may be allocated.

  • $m \geq 2$: If the count == m, reduce to $2$.
  • $m = 1$: Not changing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
  List<Integer> L = new ArrayList<>();
  int m = 1;
  int[] nums = new int[] { 1, 2, 2, 2, 2, 3, 4, 4, 5, 6, 6, 6 };
  // result:               1, 2, 2, 3, 4, 4, 5, 6, 6, 6  (m = 4)
  for (int val : nums) L.add(val);
  System.out.println("count: " + removeExtra(L, m)); // test (L, 1)
  System.out.println("List: " + L);
}

// O(N) one-pass
// index | 0  1  2  3  4  5  6  7  8  9  10  11
// m = 4 | 1  2  2  2  2  3  4  4  5  6  6   6
//         i  ----------> i
//        idx ----------> idx
//                 idx <---| (back to)
//                    (m - 2)
public static int removeExtra(List<Integer> A, int m) {
  int i = 0, idx = 0;
  while (i < A.size()) {
    int count = 0;
    int curr = A.get(i);
    // count the occurrence
    while (i < A.size() && A.get(i).equals(curr)) {
      count += 1;
      A.set(idx++, A.get(i++));
    }
    if (m >= 2 && count == m) { // min(2, m)
      idx -= (m - 2);
    }
  }
  return idx;
}