Remove Duplicates from Sorted Array - Leetcode 26 - TypeScript

Here's the Leetcode 26 solution using TypeScript.

Watch on Youtube

Leetcode 26 - Remove Duplicates from Sorted Array:

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.

Approach

The goal is to modify an array nums by removing any duplicate elements and return the new length of the modified array.

You should use two pointers:

• (i) to iterate through the array.

• (k) to keep track of the position where unique elements should be placed.

You'll loop through each element in the array and checks if the current element is less than the next element.

If it is, it means the current element is unique, so we assign its value to the position indicated by the pointer k and then increment k.

If the next element is undefined (which indicates the end of the array), you'll also add the current element to the modified portion of the array.

The last element of the original array should be considered anyways, even if it is a duplicate.

View on Excalidraw

Code Implementation

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

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < nums[i + 1]) {
      nums[k] = nums[i]
      k++
    } else if (nums[i + 1] === undefined) {
      nums[k] = nums[i]
      k++
    }
  }

  return k
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array nums.

This is because 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, which means that the algorithm uses only a fixed amount of extra space regardless of the size of the input array.

The space complexity is low because our algorithm modifies the input array in-place and only uses a constant number of variables.