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

publicstaticintdeleteDuplicates(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] publicintremoveDuplicates(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).

// 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 publicintremoveDuplicates(int[] nums){ int n = nums.length; if (n == 0) { return0; } 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.

// O(N) publicstaticintremoveOccurrence(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.