Remove Duplicates from Sorted Array II - Leetcode 80 - TypeScript

Here's the Leetcode 80 solution using TypeScript.

Watch on Youtube

Leetcode 80 - Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Approach

The goal is to modify an array of numbers by allowing at most two duplicates of each element and return the new length of the modified array.

You'll use two pointers:

• i to iterate through the array.

• k to keep track of the position where valid elements (remember you can only allow at most two duplicates) should be placed.

You'll start the loop from the third element (index 2) since the first two elements are automatically considered as part of the modified array.

Then you'll check if the current element is different from the element at position k - 2.

If it is, it means the current element is not a duplicate within the allowed limit, so you assign its value to the position indicated by the pointer k and then increment k.

This approach will allow only two duplicates of each element in the modified portion of the array.

Now k represents the new length of the modified array.

View on Excalidraw

Code Implementation

function removeDuplicates(nums: number[]): number {
  let k = 2

  for (let i = 2; i < nums.length; i++) {
    if (nums[i] !== nums[k - 2]) {
      nums[k] = nums[i]
      k++
    }
  }

  return k
}

Time Complexity

The time complexity is O(n), where n is the length of the input array nums. The algorithm iterates through each element in the array once, and the operations inside the loop take constant time.

Space Complexity

The space complexity is O(1) or constant. The algorithm modifies the input array in-place, and only uses a constant amount of extra space for variables. It doesn't require additional memory that grows with the size of the input array.