90 Valuable Interview Coding Problems — 20 Patterns Master Sheet

function moveZeroes(arr) {
  let w = 0
  for (const x of arr) if (x !== 0) arr[w++] = x
  while (w < arr.length) arr[w++] = 0
  return arr
}

// moveZeroes([0,1,0,3,12])
// i=0  val=0  write=0  → skip
// i=1  val=1  arr[0]=1  write=1
// i=2  val=0  write=1  → skip
// i=3  val=3  arr[1]=3  write=2
// i=4  val=12 arr[2]=12 write=3
// fill arr[3..4]=0
// result → [1,3,12,0,0]

// ── Demo calls — output shown on the right ──
moveZeroes([0, 1, 0, 3, 12]) // → [1, 3, 12, 0, 0]
moveZeroes([0, 0, 1]) // → [1, 0, 0]

function productExceptSelf(arr) {
  const n = arr.length
  const out = Array(n).fill(1)
  let prefix = 1
  for (let i = 0; i < n; i++) {
    out[i] = prefix
    prefix *= arr[i]
  }
  let suffix = 1
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suffix
    suffix *= arr[i]
  }
  return out
}

// productExceptSelf([1,2,3,4])
// prefix pass: out=[1,1,2,6] prefix ends 24
// suffix i=3: out[3]=6*1=6 suffix=4
// suffix i=2: out[2]=2*4=8 suffix=12
// suffix i=1: out[1]=1*12=12 suffix=24
// suffix i=0: out[0]=1*24=24
// result → [24,12,8,6]

// ── Demo calls — output shown on the right ──
productExceptSelf([1, 2, 3, 4]) // → [24, 12, 8, 6]
productExceptSelf([2, 3, 4, 5]) // → [60, 40, 30, 24]

function rotateArray(arr, k) {
  const n = arr.length
  if (!n) return arr
  k %= n
  const rev = (l, r) => {
    while (l < r) {
      ;[arr[l], arr[r]] = [arr[r], arr[l]]
      l++
      r--
    }
  }
  rev(0, n - 1)
  rev(0, k - 1)
  rev(k, n - 1)
  return arr
}

// rotateArray([1,2,3,4,5], 2)  k=2
// reverse all → [5,4,3,2,1]
// reverse [0..1] → [4,5,3,2,1]
// reverse [2..4] → [4,5,1,2,3]
// result → [4,5,1,2,3]

// ── Demo calls — output shown on the right ──
rotateArray([1, 2, 3, 4, 5], 2) // → [4, 5, 1, 2, 3]
rotateArray([1, 2], 3) // → [2, 1]

function mergeIntervals(intervals) {
  if (!intervals.length) return []
  intervals.sort((a, b) => a[0] - b[0])
  const out = [intervals[0].slice()]
  for (let i = 1; i < intervals.length; i++) {
    const last = out[out.length - 1]
    if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1])
    else out.push(intervals[i].slice())
  }
  return out
}

// mergeIntervals([[1,3],[2,6],[8,10],[15,18]])
// sort unchanged
// out=[[1,3]] → merge [2,6] → [[1,6]]
// [8,10] new → [[1,6],[8,10]]
// [15,18] new → [[1,6],[8,10],[15,18]]

// ── Demo calls — output shown on the right ──
mergeIntervals([
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18],
]) // → [[1,6],[8,10],[15,18]]
mergeIntervals([
  [1, 4],
  [4, 5],
]) // → [[1,5]]

function insertInterval(intervals, ni) {
  const out = []
  let i = 0,
    n = intervals.length
  while (i < n && intervals[i][1] < ni[0]) out.push(intervals[i++])
  while (i < n && intervals[i][0] <= ni[1]) {
    ni[0] = Math.min(ni[0], intervals[i][0])
    ni[1] = Math.max(ni[1], intervals[i][1])
    i++
  }
  out.push(ni)
  while (i < n) out.push(intervals[i++])
  return out
}

// insertInterval([[1,3],[6,9]], [2,5])
// [1,3] overlaps → merged [1,5]
// [6,9] after → [[1,5],[6,9]]

// ── Demo calls — output shown on the right ──
insertInterval(
  [
    [1, 3],
    [6, 9],
  ],
  [2, 5],
) // → [[1,5],[6,9]]
insertInterval(
  [
    [1, 2],
    [3, 5],
    [6, 7],
    [8, 10],
    [12, 16],
  ],
  [4, 8],
) // → [[1,2],[3,10],[12,16]]

function firstMissingPositive(arr) {
  const n = arr.length
  for (let i = 0; i < n; i++) {
    while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] !== arr[i]) {
      ;[arr[arr[i] - 1], arr[i]] = [arr[i], arr[arr[i] - 1]]
    }
  }
  for (let i = 0; i < n; i++) if (arr[i] !== i + 1) return i + 1
  return n + 1
}

// firstMissingPositive([3,4,-1,1])
// place 1→idx0, 3→idx2, 4→idx3 → [1,-1,3,4]
// index1 arr[1]=-1 ≠ 2 → return 2

// ── Demo calls — output shown on the right ──
firstMissingPositive([3, 4, -1, 1]) // → 2
firstMissingPositive([1, 2, 0]) // → 3

function findDuplicate(arr) {
  let slow = arr[0],
    fast = arr[0]
  do {
    slow = arr[slow]
    fast = arr[arr[fast]]
  } while (slow !== fast)
  slow = arr[0]
  while (slow !== fast) {
    slow = arr[slow]
    fast = arr[fast]
  }
  return slow
}

// findDuplicate([1,3,4,2,2])
// slow:1→3→2  fast:1→4→2→2 meet at 2
// reset slow=1, advance both → meet at 2
// result → 2

// ── Demo calls — output shown on the right ──
findDuplicate([1, 3, 4, 2, 2]) // → 2
findDuplicate([3, 1, 3, 4, 2]) // → 3

function findDisappearedNumbers(arr) {
  const n = arr.length
  for (let i = 0; i < n; i++) {
    const idx = Math.abs(arr[i]) - 1
    if (arr[idx] > 0) arr[idx] = -arr[idx]
  }
  const out = []
  for (let i = 0; i < n; i++) if (arr[i] > 0) out.push(i + 1)
  return out
}

// findDisappearedNumbers([4,3,2,7,8,2,3,1])
// negate at indices 3,2,1,6,7,1,2,0
// positive indices 4,5 → missing 5,6

// ── Demo calls — output shown on the right ──
findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1]) // → [5, 6]
findDisappearedNumbers([1, 1]) // → [2]

function findErrorNums(arr) {
  const n = arr.length
  let sum = 0,
    sq = 0
  for (const x of arr) {
    sum += x
    sq += x * x
  }
  const tSum = (n * (n + 1)) / 2
  const tSq = (n * (n + 1) * (2 * n + 1)) / 6
  const d = sum - tSum
  const dSq = sq - tSq
  const dup = (dSq / d + d) / 2
  const missing = dup - d
  return [dup, missing]
}

// findErrorNums([1,2,2,4])
// sum=9 tSum=10 d=-1  sq=25 tSq=30 dSq=-5
// dup=2 missing=3 → [2,3]

// ── Demo calls — output shown on the right ──
findErrorNums([1, 2, 2, 4]) // → [2, 3]
findErrorNums([1, 1]) // → [1, 2]

function findDuplicates(arr) {
  const out = []
  for (let i = 0; i < arr.length; i++) {
    const idx = Math.abs(arr[i]) - 1
    if (arr[idx] < 0) out.push(idx + 1)
    else arr[idx] = -arr[idx]
  }
  return out
}

// findDuplicates([4,3,2,7,8,2,3,1])
// second visit to idx1 → 2, idx2 → 3
// result → [2,3]

// ── Demo calls — output shown on the right ──
findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]) // → [2, 3]
findDuplicates([1, 1, 2]) // → [1]

function maxSubarraySum(arr) {
  let cur = arr[0],
    best = arr[0]
  for (let i = 1; i < arr.length; i++) {
    cur = Math.max(arr[i], cur + arr[i])
    best = Math.max(best, cur)
  }
  return best
}

// maxSubarraySum([-2,1,-3,4,-1,2,1,-5,4])
// cur: -2,1,-2,4,3,5,6,1,5  best max=6 at [4,-1,2,1]

// ── Demo calls — output shown on the right ──
maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) // → 6
maxSubarraySum([5, 4, -1, 7, 8]) // → 23

function maxProfit(prices) {
  let minP = Infinity,
    best = 0
  for (const p of prices) {
    minP = Math.min(minP, p)
    best = Math.max(best, p - minP)
  }
  return best
}

// maxProfit([7,1,5,3,6,4])
// minP:7,1,1,1,1  profit:0,4,2,5
// buy@1 sell@6 → 5

// ── Demo calls — output shown on the right ──
maxProfit([7, 1, 5, 3, 6, 4]) // → 5
maxProfit([7, 6, 4, 3, 1]) // → 0

function twoSumII(arr, target) {
  let l = 0,
    r = arr.length - 1
  while (l < r) {
    const s = arr[l] + arr[r]
    if (s === target) return [l + 1, r + 1]
    if (s < target) l++
    else r--
  }
  return []
}

// twoSumII([2,7,11,15], 9)
// l=0,r=3 sum=17>9 r--
// l=0,r=2 sum=13>9 r--
// l=0,r=1 sum=9 → [1,2]

// ── Demo calls — output shown on the right ──
twoSumII([2, 7, 11, 15], 9) // → [1, 2]
twoSumII([2, 3, 4], 6) // → [1, 3]

function maxArea(arr) {
  let l = 0,
    r = arr.length - 1,
    best = 0
  while (l < r) {
    best = Math.max(best, Math.min(arr[l], arr[r]) * (r - l))
    if (arr[l] < arr[r]) l++
    else r--
  }
  return best
}

// maxArea([1,8,6,2,5,4,8,3,7])
// best at l=1,r=8: min(8,7)*7=49

// ── Demo calls — output shown on the right ──
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) // → 49
maxArea([1, 1]) // → 1

function threeSum(arr) {
  arr.sort((a, b) => a - b)
  const out = []
  for (let i = 0; i < arr.length - 2; i++) {
    if (i && arr[i] === arr[i - 1]) continue
    let l = i + 1,
      r = arr.length - 1
    while (l < r) {
      const s = arr[i] + arr[l] + arr[r]
      if (s === 0) {
        out.push([arr[i], arr[l], arr[r]])
        while (l < r && arr[l] === arr[l + 1]) l++
        while (l < r && arr[r] === arr[r - 1]) r--
        l++
        r--
      } else if (s < 0) l++
      else r--
    }
  }
  return out
}

// threeSum([-1,0,1,2,-1,-4]) sorted [-4,-1,-1,0,1,2]
// i=-4: no zero sum
// i=-1: pairs → [-1,-1,2], [-1,0,1]

// ── Demo calls — output shown on the right ──
threeSum([-1, 0, 1, 2, -1, -4]) // → [[-1,-1,2],[-1,0,1]]
threeSum([0, 0, 0]) // → [[0,0,0]]

function removeDuplicates(arr) {
  if (!arr.length) return 0
  let w = 1
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[w - 1]) arr[w++] = arr[i]
  }
  return w
}

// removeDuplicates([1,1,2,2,3])
// w=1: copy 2→w=2, copy 3→w=3
// return 3

// ── Demo calls — output shown on the right ──
removeDuplicates([1, 1, 2, 2, 3]) // → 3  (array starts [1,2,3])
removeDuplicates([1, 2, 3]) // → 3

function isPalindrome(s) {
  const isAlnum = (c) => /[a-z0-9]/i.test(c)
  let l = 0,
    r = s.length - 1
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++
    while (l < r && !isAlnum(s[r])) r--
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
}

// isPalindrome("A man, a plan, a canal: Panama")
// compare a↔a, m↔m, ... all match → true

// ── Demo calls — output shown on the right ──
isPalindrome('A man, a plan, a canal: Panama') // → true
isPalindrome('race a car') // → false

function lengthOfLongestSubstring(s) {
  const last = new Map()
  let l = 0,
    best = 0
  for (let r = 0; r < s.length; r++) {
    if (last.has(s[r]) && last.get(s[r]) >= l) l = last.get(s[r]) + 1
    last.set(s[r], r)
    best = Math.max(best, r - l + 1)
  }
  return best
}

// lengthOfLongestSubstring("abcabcbb")
// window "abc" len=3 best; shrink at repeat b,c
// best stays 3

// ── Demo calls — output shown on the right ──
lengthOfLongestSubstring('abcabcbb') // → 3
lengthOfLongestSubstring('bbbbb') // → 1

function minWindow(s, t) {
  if (!t.length) return ''
  const need = new Map()
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1)
  let have = 0,
    goal = need.size,
    l = 0,
    best = '',
    bestLen = Infinity
  const win = new Map()
  for (let r = 0; r < s.length; r++) {
    const c = s[r]
    win.set(c, (win.get(c) ?? 0) + 1)
    if (need.has(c) && win.get(c) === need.get(c)) have++
    while (have === goal) {
      if (r - l + 1 < bestLen) {
        bestLen = r - l + 1
        best = s.slice(l, r + 1)
      }
      const lc = s[l++]
      if (need.has(lc) && win.get(lc) === need.get(lc)) have--
      win.set(lc, win.get(lc) - 1)
    }
  }
  return best
}

// minWindow("ADOBECODEBANC","ABC")
// valid at ADOBEC, shrink → BANC len=4 best

// ── Demo calls — output shown on the right ──
minWindow('ADOBECODEBANC', 'ABC') // → "BANC"
minWindow('a', 'a') // → "a"

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false
  const cnt = (s) => {
    const m = Array(26).fill(0)
    for (const c of s) m[c.charCodeAt(0) - 97]++
    return m
  }
  const a = cnt(s1),
    b = cnt(s2.slice(0, s1.length))
  const eq = () => a.every((v, i) => v === b[i])
  if (eq()) return true
  for (let i = s1.length; i < s2.length; i++) {
    b[s2.charCodeAt(i - s1.length) - 97]--
    b[s2.charCodeAt(i) - 97]++
    if (eq()) return true
  }
  return false
}

// checkInclusion("ab","eidbaooo")
// window "dba" matches ab permutation → true

// ── Demo calls — output shown on the right ──
checkInclusion('ab', 'eidbaooo') // → true
checkInclusion('ab', 'eidboaoo') // → false

function findAnagrams(s, p) {
  if (p.length > s.length) return []
  const diff = Array(26).fill(0)
  for (let i = 0; i < p.length; i++) {
    diff[p.charCodeAt(i) - 97]++
    diff[s.charCodeAt(i) - 97]--
  }
  const out = []
  const ok = () => diff.every((x) => x === 0)
  if (ok()) out.push(0)
  for (let i = p.length; i < s.length; i++) {
    diff[s.charCodeAt(i - p.length) - 97]++
    diff[s.charCodeAt(i) - 97]--
    if (ok()) out.push(i - p.length + 1)
  }
  return out
}

// findAnagrams("cbaebabacd","abc")
// index0 "cba", index6 "bac" → [0,6]

// ── Demo calls — output shown on the right ──
findAnagrams('cbaebabacd', 'abc') // → [0, 6]
findAnagrams('abab', 'ab') // → [0, 1, 2]

function findMaxAverage(arr, k) {
  let sum = 0
  for (let i = 0; i < k; i++) sum += arr[i]
  let best = sum
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k]
    best = Math.max(best, sum)
  }
  return best / k
}

// findMaxAverage([1,12,-5,-6,50,3], 4)
// sums: 2, 51 best → 51/4=12.75

// ── Demo calls — output shown on the right ──
findMaxAverage([1, 12, -5, -6, 50, 3], 4) // → 12.75
findMaxAverage([5], 1) // → 5

function subarraySum(arr, k) {
  const freq = new Map([[0, 1]])
  let sum = 0,
    count = 0
  for (const x of arr) {
    sum += x
    count += freq.get(sum - k) ?? 0
    freq.set(sum, (freq.get(sum) ?? 0) + 1)
  }
  return count
}

// subarraySum([1,1,1], 2)
// prefix 1→0, 2→1 hit, 3→1 hit → 2

// ── Demo calls — output shown on the right ──
subarraySum([1, 1, 1], 2) // → 2
subarraySum([1, 2, 3], 3) // → 2

function checkSubarraySum(arr, k) {
  const modIdx = new Map([[0, -1]])
  let sum = 0
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i]
    const mod = k === 0 ? sum : sum % k
    if (modIdx.has(mod)) {
      if (i - modIdx.get(mod) >= 2) return true
    } else modIdx.set(mod, i)
  }
  return false
}

// checkSubarraySum([23,2,4,6,7], 6)
// mod 2 at idx1 and idx4 len≥2 → true

// ── Demo calls — output shown on the right ──
checkSubarraySum([23, 2, 4, 6, 7], 6) // → true
checkSubarraySum([23, 2, 6, 4, 7], 6) // → true

class NumArray {
  constructor(nums) {
    this.prefix = [0]
    for (const x of nums) this.prefix.push(this.prefix.at(-1) + x)
  }
  sumRange(l, r) {
    return this.prefix[r + 1] - this.prefix[l]
  }
}

// NumArray([-2,0,3,-4,2,-1])
// prefix [0,-2,-2,1,-3,-1,-2]
// sumRange(0,2) = prefix[3]-prefix[0] = 1

// ── Demo calls — output shown on the right ──
new NumArray([-2, 0, 3, -4, 2, -1]).sumRange(0, 2) // → 1
new NumArray([-2, 0, 3, -4, 2, -1]).sumRange(2, 5) // → -1

function productExceptSelfPrefix(arr) {
  const n = arr.length,
    out = Array(n).fill(1)
  let left = 1
  for (let i = 0; i < n; i++) {
    out[i] = left
    left *= arr[i]
  }
  let right = 1
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right
    right *= arr[i]
  }
  return out
}

// productExceptSelfPrefix([1,2,3,4])
// left out=[1,1,2,6]; right multiply → [24,12,8,6]

// ── Demo calls — output shown on the right ──
productExceptSelfPrefix([1, 2, 3, 4]) // → [24, 12, 8, 6]
productExceptSelfPrefix([-1, 1, 0, -3, 3]) // → [0, 0, 9, 0, 0]

function twoSum(arr, target) {
  const map = new Map()
  for (let i = 0; i < arr.length; i++) {
    const need = target - arr[i]
    if (map.has(need)) return [map.get(need), i]
    map.set(arr[i], i)
  }
  return []
}

// twoSum([2,7,11,15], 9)
// i=0 map{2:0}; i=1 need=2 found → [0,1]

// ── Demo calls — output shown on the right ──
twoSum([2, 7, 11, 15], 9) // → [0, 1]
twoSum([3, 2, 4], 6) // → [1, 2]

function groupAnagrams(strs) {
  const map = new Map()
  for (const s of strs) {
    const key = [...s].sort().join('')
    if (!map.has(key)) map.set(key, [])
    map.get(key).push(s)
  }
  return [...map.values()]
}

// groupAnagrams(["eat","tea","tan","ate","nat","bat"])
// keys aet→3 words, ant→2, abt→bat

// ── Demo calls — output shown on the right ──
groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']) // → [["eat","tea","ate"],["tan","nat"],["bat"]]
groupAnagrams(['']) // → [[""]]

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false
  const a = new Map(),
    b = new Map()
  for (let i = 0; i < s.length; i++) {
    if (!a.has(s[i])) a.set(s[i], t[i])
    if (!b.has(t[i])) b.set(t[i], s[i])
    if (a.get(s[i]) !== t[i] || b.get(t[i]) !== s[i]) return false
  }
  return true
}

// isIsomorphic("egg","add")
// e→a, g→d consistent → true

// ── Demo calls — output shown on the right ──
isIsomorphic('egg', 'add') // → true
isIsomorphic('foo', 'bar') // → false

function isHappy(n) {
  const seen = new Set()
  const next = (x) =>
    String(x)
      .split('')
      .reduce((s, d) => s + d * d, 0)
  while (n !== 1 && !seen.has(n)) {
    seen.add(n)
    n = next(n)
  }
  return n === 1
}

undefined

// ── Demo calls — output shown on the right ──
isHappy(19) // → true
isHappy(2) // → false

class ListNode {
  constructor(val, next = null) {
    this.val = val
    this.next = next
  }
}
function hasCycle(head) {
  let slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

// hasCycle 3→2→0→-4→(back to 2)
// slow:3,2,0,-4,2  fast:3,0,2,0 meet → true

// ── Demo calls — output shown on the right ──
hasCycle(/* 3→2→0→-4↘ */) // → true
hasCycle(/* 1→2 */) // → false

function detectCycle(head) {
  let slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      slow = head
      while (slow !== fast) {
        slow = slow.next
        fast = fast.next
      }
      return slow
    }
  }
  return null
}

// detectCycle entry at node val=2
// meet inside cycle; reset slow=head → both reach node 2

// ── Demo calls — output shown on the right ──
detectCycle(/* cycle entry at 2 */) // → node 2
detectCycle(/* no cycle */) // → null

function isHappyFloyd(n) {
  const next = (x) =>
    String(x)
      .split('')
      .reduce((s, d) => s + d * d, 0)
  let slow = n,
    fast = next(n)
  while (fast !== 1 && slow !== fast) {
    slow = next(slow)
    fast = next(next(fast))
  }
  return fast === 1
}

// isHappyFloyd(19)
// slow/fast on digit-square chain → reaches 1

// ── Demo calls — output shown on the right ──
isHappyFloyd(19) // → true
isHappyFloyd(2) // → false

function findDuplicateFloyd(arr) {
  let slow = arr[0],
    fast = arr[0]
  do {
    slow = arr[slow]
    fast = arr[arr[fast]]
  } while (slow !== fast)
  slow = arr[0]
  while (slow !== fast) {
    slow = arr[slow]
    fast = arr[fast]
  }
  return slow
}

// findDuplicateFloyd([1,3,4,2,2])
// index graph cycle entry → 2

// ── Demo calls — output shown on the right ──
findDuplicateFloyd([1, 3, 4, 2, 2]) // → 2
findDuplicateFloyd([3, 1, 3, 4, 2]) // → 3

function reverseList(head) {
  let prev = null,
    cur = head
  while (cur) {
    const nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
  }
  return prev
}

// reverseList 1→2→3
// prev: null,1,2  head ends 3→2→1

// ── Demo calls — output shown on the right ──
reverseList(/* 1→2→3→4→5 */) // → 5→4→3→2→1
reverseList(/* 1→2 */) // → 2→1

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0)
  let tail = dummy
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1
      l1 = l1.next
    } else {
      tail.next = l2
      l2 = l2.next
    }
    tail = tail.next
  }
  tail.next = l1 || l2
  return dummy.next
}

// merge 1→2→4 and 1→3→4
// pick 1,1,2,3,4,4 → merged list

// ── Demo calls — output shown on the right ──
mergeTwoLists(/*1→2→4*/, /*1→3→4*/)  // → 1→1→2→3→4→4
mergeTwoLists(null, /*0*/)  // → 0

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head)
  let slow = dummy,
    fast = dummy
  for (let i = 0; i <= n; i++) fast = fast.next
  while (fast) {
    slow = slow.next
    fast = fast.next
  }
  slow.next = slow.next.next
  return dummy.next
}

// removeNthFromEnd 1→2→3→4→5 n=2
// fast stops at null; slow before 4 → skip 5

// ── Demo calls — output shown on the right ──
removeNthFromEnd(/*1→2→3→4→5*/, 2)  // → 1→2→3→5
removeNthFromEnd(/*1*/, 1)  // → null

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0)
  let tail = dummy,
    carry = 0
  while (l1 || l2 || carry) {
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
    carry = Math.floor(sum / 10)
    tail.next = new ListNode(sum % 10)
    tail = tail.next
    l1 = l1?.next ?? null
    l2 = l2?.next ?? null
  }
  return dummy.next
}

// addTwoNumbers 342+465=807 → 7→0→8

// ── Demo calls — output shown on the right ──
addTwoNumbers(/*2→4→3*/, /*5→6→4*/)  // → 7→0→8
addTwoNumbers(/*0*/, /*0*/)  // → 0

class RandomNode {
  constructor(val) {
    this.val = val
    this.next = null
    this.random = null
  }
}
function copyRandomList(head) {
  if (!head) return null
  const map = new Map()
  let cur = head
  while (cur) {
    map.set(cur, new RandomNode(cur.val))
    cur = cur.next
  }
  cur = head
  while (cur) {
    map.get(cur).next = cur.next ? map.get(cur.next) : null
    map.get(cur).random = cur.random ? map.get(cur.random) : null
    cur = cur.next
  }
  return map.get(head)
}

// copyRandomList: clone each node, map old→new, wire links

// ── Demo calls — output shown on the right ──
copyRandomList(/* [[7,null],[13,0],[11,4],[10,2],[1,0]] */) // → deep copy
copyRandomList(null) // → null

function swapPairs(head) {
  const dummy = new ListNode(0, head)
  let prev = dummy
  while (prev.next && prev.next.next) {
    const a = prev.next,
      b = a.next
    a.next = b.next
    b.next = a
    prev.next = b
    prev = a
  }
  return dummy.next
}

// swapPairs 1→2→3→4
// swap(1,2) then (3,4) → 2→1→4→3

// ── Demo calls — output shown on the right ──
swapPairs(/*1→2→3→4*/) // → 2→1→4→3
swapPairs(/*1→2→3*/) // → 2→1→3

function rotateRight(head, k) {
  if (!head || !head.next || !k) return head
  let len = 1,
    tail = head
  while (tail.next) {
    len++
    tail = tail.next
  }
  k %= len
  if (!k) return head
  tail.next = head
  let steps = len - k,
    cur = tail
  while (steps--) cur = cur.next
  const newHead = cur.next
  cur.next = null
  return newHead
}

// rotateRight 1→2→3→4→5 k=2 len=5
// tail→head; break before node4 → 4→5→1→2→3

// ── Demo calls — output shown on the right ──
rotateRight(/*1→2→3→4→5*/, 2)  // → 4→5→1→2→3
rotateRight(/*0→1→2*/, 4)  // → 2→0→1

function binarySearch(arr, target) {
  let lo = 0,
    hi = arr.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (arr[mid] === target) return mid
    if (arr[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

// binarySearch([-1,0,3,5,9,12], 9)
// lo,hi: 0,5 mid=2 val3<9 → lo=3
// 3,5 mid=4 val9 → return 4

// ── Demo calls — output shown on the right ──
binarySearch([-1, 0, 3, 5, 9, 12], 9) // → 4
binarySearch([-1, 0, 3, 5, 9, 12], 2) // → -1

function searchRotated(arr, target) {
  let lo = 0,
    hi = arr.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (arr[mid] === target) return mid
    if (arr[lo] <= arr[mid]) {
      if (arr[lo] <= target && target < arr[mid]) hi = mid - 1
      else lo = mid + 1
    } else {
      if (arr[mid] < target && target <= arr[hi]) lo = mid + 1
      else hi = mid - 1
    }
  }
  return -1
}

// searchRotated([4,5,6,7,0,1,2], 0)
// left half sorted; 0 not in [4,7) → lo=mid+1 → find idx4

// ── Demo calls — output shown on the right ──
searchRotated([4, 5, 6, 7, 0, 1, 2], 0) // → 4
searchRotated([4, 5, 6, 7, 0, 1, 2], 3) // → -1

function findPeakElement(arr) {
  let lo = 0,
    hi = arr.length - 1
  while (lo < hi) {
    const mid = (lo + hi) >> 1
    if (arr[mid] < arr[mid + 1]) lo = mid + 1
    else hi = mid
  }
  return lo
}

// findPeakElement([1,2,3,1])
// mid=1 2<3 → lo=2; lo=hi=2 peak idx2 val3

// ── Demo calls — output shown on the right ──
findPeakElement([1, 2, 3, 1]) // → 2
findPeakElement([1, 2, 1, 3, 5, 6, 4]) // → 5

function findMedianSortedArrays(a, b) {
  if (a.length > b.length) [a, b] = [b, a]
  const m = a.length,
    n = b.length,
    half = (m + n + 1) >> 1
  let lo = 0,
    hi = m
  while (lo <= hi) {
    const i = (lo + hi) >> 1,
      j = half - i
    const aL = i ? a[i - 1] : -Infinity,
      aR = i < m ? a[i] : Infinity
    const bL = j ? b[j - 1] : -Infinity,
      bR = j < n ? b[j] : Infinity
    if (aL <= bR && bL <= aR) {
      return (m + n) % 2 ? Math.max(aL, bL) : (Math.max(aL, bL) + Math.min(aR, bR)) / 2
    }
    if (aL > bR) hi = i - 1
    else lo = i + 1
  }
  return 0
}

// findMedianSortedArrays([1,3],[2])
// partition i=1,j=0 → left [1] right [2,3] median=2

// ── Demo calls — output shown on the right ──
findMedianSortedArrays([1, 3], [2]) // → 2
findMedianSortedArrays([1, 2], [3, 4]) // → 2.5

function isValid(s) {
  const map = { ')': '(', ']': '[', '}': '{' }
  const st = []
  for (const c of s) {
    if ('([{'.includes(c)) st.push(c)
    else if (!st.length || st.pop() !== map[c]) return false
  }
  return st.length === 0
}

// isValid("()[]{}")
// push ( [ { ; pop matches → empty stack true

// ── Demo calls — output shown on the right ──
isValid('()[]{}') // → true
isValid('(]') // → false

function dailyTemperatures(arr) {
  const out = Array(arr.length).fill(0),
    st = []
  for (let i = 0; i < arr.length; i++) {
    while (st.length && arr[i] > arr[st.at(-1)]) {
      const j = st.pop()
      out[j] = i - j
    }
    st.push(i)
  }
  return out
}

// dailyTemperatures([73,74,75,...])
// stack resolves warmer days → wait counts

// ── Demo calls — output shown on the right ──
dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) // → [1,1,4,2,1,1,0,0]
dailyTemperatures([30, 40, 50, 60]) // → [1,1,1,0]

function nextGreaterElements(arr) {
  const out = Array(arr.length).fill(-1),
    st = []
  for (let i = 0; i < arr.length; i++) {
    while (st.length && arr[i] > arr[st.at(-1)]) {
      out[st.pop()] = arr[i]
    }
    st.push(i)
  }
  return out
}

// nextGreaterElements([2,1,2,4,3])
// idx0→4 idx1→2 idx2→4 idx3,4→-1

// ── Demo calls — output shown on the right ──
nextGreaterElements([2, 1, 2, 4, 3]) // → [4,2,4,-1,-1]
nextGreaterElements([5, 4, 3, 2, 1]) // → [-1,-1,-1,-1,-1]

function largestRectangleArea(heights) {
  const st = [],
    n = heights.length
  let best = 0
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i]
    while (st.length && h < heights[st.at(-1)]) {
      const hi = st.pop()
      const w = st.length ? i - st.at(-1) - 1 : i
      best = Math.max(best, heights[hi] * w)
    }
    st.push(i)
  }
  return best
}