Array patterns · Lesson 6 of 23

Two pointers

Two indexes moving through an array instead of nested loops: O(n²) becomes O(n).

12 minutes3 games

A simple idea that cracks many problems: instead of trying every pair (O(n²)), place two indexes and move them cleverly. Two common shapes:

From both ends inward: one at the start, one at the end, closing in (palindromes, pair sums in a sorted array, the biggest water container).
Fast and slow in the same direction: one reads, one writes (removing duplicates, moving zeros).

JavaScript

// Sorted array: find two numbers adding up to target
function pairInSorted(nums, target) {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++      // need a bigger sum: move the small side up
    else right--                  // need a smaller sum: move the big side down
  }
  return []
}

console.log(pairInSorted([1, 3, 4, 6, 9, 11], 13))
console.log(pairInSorted([1, 2, 3], 100))

Step by step1 / 5

1const nums = [1, 3, 4, 6, 9, 11]
▶let l = 0, r = 5
3// 1 + 11 = 12 < 13
4l++
5// 3 + 11 = 14 > 13
6r--
7// 3 + 9 = 12 < 13
8l++
9console.log(nums[l] + nums[r])

Variables

l	0 → 1
r	5 → 11

Output

…

1 + 11 = 12 is below 13. Anything paired with 1 is smaller still, so 1 is useless.

Every step rules one element out for good, so there are at most n steps.

Reader and writer

JavaScript

// Remove duplicates from a sorted array in place; return the new length
function dedupe(nums) {
  let write = 1
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read]
  }
  return write
}

const arr = [1, 1, 2, 3, 3, 3, 4]
const n = dedupe(arr)
console.log(n, arr.slice(0, n))

Quick question

In "container with most water" (walls of given heights; water between two walls = the shorter one × the distance), the pointers are at the ends. Which do you move?

Complete the code

Complete the two-pointer palindrome check.

function isPal(s) {
  let i = 0, j = s.length - 1
  while (i < j) {
    if (s[i] !== s[j]) return 
    i++
    --
  }
  return true
}

Exercise

Write squaresSorted(nums): the array is sorted (with negatives); return the squares sorted ascending in O(n), without sort. It must print [0, 1, 9, 16, 100].

Expected output: [0, 1, 9, 16, 100]

JavaScript

function squaresSorted(nums) {
  
}

console.log(squaresSorted([-4, -1, 0, 3, 10]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 3 games

DSA

Array patterns · Lesson 6 of 23

Two pointers

Two indexes moving through an array instead of nested loops: O(n²) becomes O(n).

12 minutes3 games

A simple idea that cracks many problems: instead of trying every pair (O(n²)), place two indexes and move them cleverly. Two common shapes:

From both ends inward: one at the start, one at the end, closing in (palindromes, pair sums in a sorted array, the biggest water container).
Fast and slow in the same direction: one reads, one writes (removing duplicates, moving zeros).

JavaScript

// Sorted array: find two numbers adding up to target
function pairInSorted(nums, target) {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++      // need a bigger sum: move the small side up
    else right--                  // need a smaller sum: move the big side down
  }
  return []
}

console.log(pairInSorted([1, 3, 4, 6, 9, 11], 13))
console.log(pairInSorted([1, 2, 3], 100))

Step by step1 / 5

1const nums = [1, 3, 4, 6, 9, 11]
▶let l = 0, r = 5
3// 1 + 11 = 12 < 13
4l++
5// 3 + 11 = 14 > 13
6r--
7// 3 + 9 = 12 < 13
8l++
9console.log(nums[l] + nums[r])

Variables

l	0 → 1
r	5 → 11

Output

…

1 + 11 = 12 is below 13. Anything paired with 1 is smaller still, so 1 is useless.

Every step rules one element out for good, so there are at most n steps.

Reader and writer

JavaScript

// Remove duplicates from a sorted array in place; return the new length
function dedupe(nums) {
  let write = 1
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read]
  }
  return write
}

const arr = [1, 1, 2, 3, 3, 3, 4]
const n = dedupe(arr)
console.log(n, arr.slice(0, n))

Quick question

In "container with most water" (walls of given heights; water between two walls = the shorter one × the distance), the pointers are at the ends. Which do you move?

Complete the code

Complete the two-pointer palindrome check.

function isPal(s) {
  let i = 0, j = s.length - 1
  while (i < j) {
    if (s[i] !== s[j]) return 
    i++
    --
  }
  return true
}

Exercise

Write squaresSorted(nums): the array is sorted (with negatives); return the squares sorted ascending in O(n), without sort. It must print [0, 1, 9, 16, 100].

Expected output: [0, 1, 9, 16, 100]

JavaScript

function squaresSorted(nums) {
  
}

console.log(squaresSorted([-4, -1, 0, 3, 10]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 3 games