Array patterns · Lesson 7 of 23

Sliding window

Longest or shortest contiguous part meeting a condition: a window that grows and shrinks in one pass.

13 minutes3 games

Whenever a problem asks for the longest, shortest or count of contiguous parts (substrings or subarrays), think sliding window: two indexes start and end frame a window. end grows it; when it becomes invalid, start shrinks it.

Each element enters and leaves the window once, so the whole thing is O(n) rather than O(n²) for trying every part.

JavaScript

// Longest substring without repeating letters
function longestUnique(s) {
  const lastSeen = new Map()
  let start = 0, best = 0
  for (let end = 0; end < s.length; end++) {
    const ch = s[end]
    // The letter is inside the window: move start just past its last position
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) start = lastSeen.get(ch) + 1
    lastSeen.set(ch, end)
    best = Math.max(best, end - start + 1)
  }
  return best
}

console.log(longestUnique("abcabcbb"), longestUnique("bbbb"), longestUnique("pwwkew"))

s =

p[0]

w[1]

w[2]

k[3]

e[4]

w[5]

In pwwkew the longest repeat-free window is wke (length 3). When the third w arrives, start jumps past the w inside the window.

The template

JavaScript

let start = 0
for (let end = 0; end < n; end++) {
  // 1) add item[end] to the window's state (a count, a sum, a map…)
  while (/* the window is invalid */ false) {
    // 2) remove item[start] from the state
    start++
  }
  // 3) the window [start, end] is valid: update the answer
}

What's the output?

// Fixed window: best sum of 3 consecutive numbers
const nums = [2, 1, 5, 1, 3, 2]
let sum = nums[0] + nums[1] + nums[2], best = sum
for (let i = 3; i < nums.length; i++) {
  sum += nums[i] - nums[i - 3]
  best = Math.max(best, sum)
}
console.log(best)

What will this code print?

Spot the bug

This should return the length of the shortest part with sum ≥ target. One line makes it wrong. Which?

Exercise

Write maxAverage(nums, k) returning the largest sum of k consecutive numbers with an O(n) fixed window. It must print 9 14.

Expected output: 9 14

JavaScript

function maxAverage(nums, k) {
  
}

console.log(maxAverage([2, 1, 5, 1, 3, 2], 3), maxAverage([7, 7, 0, 1], 2))

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 7 of 23

Sliding window

Longest or shortest contiguous part meeting a condition: a window that grows and shrinks in one pass.

13 minutes3 games

Each element enters and leaves the window once, so the whole thing is O(n) rather than O(n²) for trying every part.

JavaScript

// Longest substring without repeating letters
function longestUnique(s) {
  const lastSeen = new Map()
  let start = 0, best = 0
  for (let end = 0; end < s.length; end++) {
    const ch = s[end]
    // The letter is inside the window: move start just past its last position
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) start = lastSeen.get(ch) + 1
    lastSeen.set(ch, end)
    best = Math.max(best, end - start + 1)
  }
  return best
}

console.log(longestUnique("abcabcbb"), longestUnique("bbbb"), longestUnique("pwwkew"))

s =

p[0]

w[1]

w[2]

k[3]

e[4]

w[5]

In pwwkew the longest repeat-free window is wke (length 3). When the third w arrives, start jumps past the w inside the window.

The template

JavaScript

let start = 0
for (let end = 0; end < n; end++) {
  // 1) add item[end] to the window's state (a count, a sum, a map…)
  while (/* the window is invalid */ false) {
    // 2) remove item[start] from the state
    start++
  }
  // 3) the window [start, end] is valid: update the answer
}

What's the output?

// Fixed window: best sum of 3 consecutive numbers
const nums = [2, 1, 5, 1, 3, 2]
let sum = nums[0] + nums[1] + nums[2], best = sum
for (let i = 3; i < nums.length; i++) {
  sum += nums[i] - nums[i - 3]
  best = Math.max(best, sum)
}
console.log(best)

What will this code print?

Spot the bug

This should return the length of the shortest part with sum ≥ target. One line makes it wrong. Which?

Exercise

Write maxAverage(nums, k) returning the largest sum of k consecutive numbers with an O(n) fixed window. It must print 9 14.

Expected output: 9 14

JavaScript

function maxAverage(nums, k) {
  
}

console.log(maxAverage([2, 1, 5, 1, 3, 2], 3), maxAverage([7, 7, 0, 1], 2))

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