Remove Duplicates from Sorted Array

NeetCode: Remove Duplicates from Sorted Array · LeetCode: 26. Remove Duplicates from Sorted Array · Difficulty: Easy

Given an array nums sorted in non-decreasing order, remove the duplicates in place so each unique value appears once. Return k, the number of unique values; the first k elements of nums must hold them in order. The contents after position k do not matter.

Example

Text

Input:  nums = [1, 1, 2]                          Output: 2, nums = [1, 2, _]
Input:  nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]     Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Brute force: collect uniques in a helper array

Build a new array (with a count of how many slots are used) containing each value that differs from the previous one, then copy it over the front of nums. It is linear but uses O(n) extra memory, while the problem asks for an in-place solution.

Java

import java.util.Arrays;

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] uniq = new int[nums.length];
        int count = 0;
        for (int x : nums) {
            if (count == 0 || uniq[count - 1] != x) {
                uniq[count++] = x;
            }
        }
        for (int i = 0; i < count; i++) {
            nums[i] = uniq[i];
        }
        return count;
    }
}

public class Main {
    static void show(int[] nums, int k) {
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(nums, k)));
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1, 1, 2};
        show(a, s.removeDuplicates(a));
        int[] b = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        show(b, s.removeDuplicates(b));
        int[] c = {};
        show(c, s.removeDuplicates(c));
    }
}

Output

2 [1, 2]
5 [0, 1, 2, 3, 4]
0 []

Time: O(n). Space: O(n).

Optimal: read pointer and write pointer

Because the array is sorted, equal values sit next to each other, so a value is new exactly when it differs from the last one kept. Let w be the next slot to write. Scan with a read pointer r; whenever nums[r] differs from nums[w - 1] (the last kept value), copy it to nums[w] and advance w. The first element is always kept.

Java

import java.util.Arrays;

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int w = 1;
        for (int r = 1; r < nums.length; r++) {
            if (nums[r] != nums[w - 1]) {
                nums[w] = nums[r];
                w++;
            }
        }
        return w;
    }
}

public class Main {
    static void show(int[] nums, int k) {
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(nums, k)));
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = {1, 1, 2};
        show(a, s.removeDuplicates(a));
        int[] b = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        show(b, s.removeDuplicates(b));
        int[] c = {};
        show(c, s.removeDuplicates(c));
    }
}

Output

2 [1, 2]
5 [0, 1, 2, 3, 4]
0 []

Time: O(n). Space: O(1).

Both are linear in time; the second uses constant memory. w >= 1 inside the loop, so nums[w - 1] is always a valid index. The show helper prints only the first k elements with Arrays.copyOf, because the rest of the array is unspecified.