Topics
Two Pointers

Reverse String (opens in a new tab)

  • Use two pointers to swap the items between left and right
  • Continue swapping until left is less than right
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify the string in-place instead
 */
var reverseString = function (s) {
  const length = s.length;
 
  for (let left = 0, right = length - 1; left < right; left++, right--) {
    // swap the items between left and right
    const temp = s[left];
    s[left] = s[right];
    s[right] = temp;
  }
};
Complexity
  • Time: O(n)
  • Space: O(1)

Remove Duplicates from Sorted Array (opens in a new tab)

  • Use 2 pointers to keep track of the current and next unique element
  • Iterate through the array and update the next unique element when a new unique element is found
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let pointer = -1;
 
  for (let i = 0; i < nums.length; i++) {
    if (nums[pointer] !== nums[i]) {
      // Found a new unique element
      pointer++;
      nums[pointer] = nums[i];
    }
  }
 
  return pointer + 1; // Return the length of the unique elements
};
Complexity
  • Time: O(n)
  • Space: O(1)

Two Sum II - Input Array Is Sorted (opens in a new tab)

  • As the array is sorted, we can use two pointers approach to find the sum of two numbers
  • If the sum of the two numbers is equal to the target, return the indices
  • If the sum is less than the target, move the left pointer to the right else move the right pointer to the left
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  let i = 0, j = numbers.length - 1;
 
  while (i < j) {
    const sum = numbers[i] + numbers[j];
 
    if (sum === target) {
      return [i + 1, j + 1];
    } else if (target < sum) {
      j--;
    } else if (target > sum) {
      i++;
    }
  }
};
Complexity
  • Time: O(n)
  • Space: O(1)
Sliding WindowStack