[Leetcode] 26. Remove Duplicates from Sorted Array

Table of Contents

Description

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge: The judge will test the solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;

for (int i = 0; i < k; ++i) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

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

Approach

The input array nums is sorted with duplicates adjacent. Using a two-pointer technique, we efficiently identify unique values: one pointer iterates through the array, while another (uniqueCount) tracks the position for unique elements. We move each unique value to its correct position in-place, ensuring the first k elements contain unique values in their original order, all in a single pass without extra space.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  // The counter for unique numbers.
  let uniqueCount = 0;
  // The last seen unique number.
  let lastUniqueNum;

  for (num of nums) {
    // Determine if the current number is different from the last unique number.
    const isUnique = num !== lastUniqueNum;

    // If the number is not unique, skip to the next iteration.
    if (!isUnique) continue;

    // Place the unique number at the current uniqueCount index.
    nums[uniqueCount] = num;

    // Update the last seen unique number.
    lastUniqueNum = num;

    // Increment the unique count.
    uniqueCount++;
  }

  return uniqueCount;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n)$, where $n$ is the length of the input array nums. We iterate through the array once, performing constant-time operations for each element.

Space Complexity

The space complexity is $O(1)$ — We use only a constant amount of extra space.