Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

🔥 Two pointers algorithm in javascript

🔥 Two pointers for sorted array 

nums.sort((a, b) => a - b);

let left = 0;
let right = N - 1;

while (left < right) {
  if (CONDITION === target) {
    // do some logic for matching case
  } else if (CONDITION < target) {
    // small. neet to increase
    left += 1;
  } else if (CONDITION > target) {
    // large. neet to decrease
    right -= 1;
  }
}

nums.sort((a, b) => a - b);

let left = 0;
let right = N - 1;

while (left < right) {
  // do some logic here with left and right

  if (CONDITION) {
    left += 1;
  } else {
    right -= 1;
  }
}

🗒️ Typical problems

Lists

🔥 Expand around the corner 

// odd
            [i]
1:          LEFT
            RIGHT
3:   LEFT-1        RIGHT+1

// even
           [i, i + 1]
2:         LEFT RIGHT
4:  LEFT-1            RIGHT+1
  • Check values in two pointers from center to the corner.
var longestPalindrome = function (s) {
  const N = s.length;

  let left = -1;
  let right = -1;
  let max = -Infinity;
  let maxValue = [left, right];
  for (let i = 0; i < N; i += 1) {
    // odd
    [left, right] = [i, i];
    while (0 <= left && right < N && s[left] === s[right]) {
      if (max < right - left + 1) {
        max = right - left + 1;
        maxValue = [left, right];
      }
      left -= 1;
      right += 1;
    }

    // even
    [left, right] = [i, i + 1];
    while (0 <= left && right < N && s[left] === s[right]) {
      if (max < right - left + 1) {
        max = right - left + 1;
        maxValue = [left, right];
      }
      left -= 1;
      right += 1;
    }
  }
  const [start, end] = maxValue;
  return s.slice(start, end + 1);
};

🗒️ Typical problems

🔥 Two pointers for linked-list

  • slow and fast pointer for detecting the cycle of the linked list.
var hasCycle = function (head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
};

🗒️ Typical problems

📚 References