Problem Solving

function maxProfit(prices) {
  // One pass: track the lowest price so far and the best profit so far
  let best = 0, lowest = Infinity
  for (const p of prices) {
    lowest = Math.min(lowest, p)
    best = Math.max(best, p - lowest)
  }
  return best
}

// The tests come straight from the contract and the edge cases
const cases = [
  [[7, 1, 5, 3, 6, 4], 5],
  [[], 0],
  [[5], 0],
  [[5, 4, 3], 0],
  [[2, 2, 2], 0],
  [[3, 1, 10], 9],
]
for (const [input, want] of cases) {
  const got = maxProfit(input)
  console.log(got === want ? "ok  " : "FAIL", JSON.stringify(input), "→", got)
}

function hasDuplicateSlow(items) {          // O(n²): every pair
  for (let i = 0; i < items.length; i++)
    for (let j = i + 1; j < items.length; j++)
      if (items[i] === items[j]) return true
  return false
}
function hasDuplicateFast(items) {          // O(n): one pass, a Set remembers
  const seen = new Set()
  for (const x of items) {
    if (seen.has(x)) return true
    seen.add(x)
  }
  return false
}

const data = Array.from({ length: 3000 }, (_, i) => i)     // no duplicates → worst case for both
for (const fn of [hasDuplicateSlow, hasDuplicateFast]) {
  const t = Date.now()
  fn(data)
  const ms = Date.now() - t
  console.log(fn.name.padEnd(18), ms > 40 ? "slow (100s of ms)" : "fast (a few ms)")
}

// Count operations instead of timing — deterministic
function countOps(n) {
  let ops = 0
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) ops++          // n²
  let k = n, halvings = 0
  while (k > 1) { k = Math.floor(k / 2); halvings++ }                    // log n
  return { n, squared: ops, log: halvings }
}
console.log(countOps(8), countOps(1024))

function pairWithSum(sortedNums, target) {
  let lo = 0, hi = sortedNums.length - 1
  while (lo < hi) {
    const s = sortedNums[lo] + sortedNums[hi]
    if (s === target) return [sortedNums[lo], sortedNums[hi]]
    if (s < target) lo++            // need a bigger sum
    else hi--                       // need a smaller sum
  }
  return null
}
console.log(pairWithSum([1, 3, 4, 6, 8, 11], 10), pairWithSum([1, 3, 4, 6, 8, 11], 100))

function longestUniqueSubstring(s) {
  // Expand right; when a repeat appears, jump left past its last position
  const lastSeen = new Map()
  let left = 0, best = 0
  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) left = lastSeen.get(ch) + 1
    lastSeen.set(ch, right)
    best = Math.max(best, right - left + 1)
  }
  return best
}
console.log(longestUniqueSubstring("abcabcbb"), longestUniqueSubstring("bbbb"), longestUniqueSubstring(""))

function maxSumWindow(nums, k) {
  // Fixed size: add the new right, drop the old left — never re-sum
  let window = 0
  for (let i = 0; i < k; i++) window += nums[i]
  let best = window
  for (let i = k; i < nums.length; i++) {
    window += nums[i] - nums[i - k]
    best = Math.max(best, window)
  }
  return best
}
console.log(maxSumWindow([2, 1, 5, 1, 3, 2], 3))

// Fast/slow pointers: is there a cycle? (Floyd)
function hasCycle(next, start) {
  let slow = start, fast = start
  while (fast !== null && next[fast] !== null) {
    slow = next[slow]; fast = next[next[fast]]
    if (slow === fast) return true
  }
  return false
}
console.log(hasCycle({ a: "b", b: "c", c: "a" }, "a"), hasCycle({ a: "b", b: null }, "a"))

function twoSum(nums, target) {
  const seen = new Map()                 // value → index
  for (let i = 0; i < nums.length; i++) {
    if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i]
    seen.set(nums[i], i)
  }
  return null
}
console.log(twoSum([2, 7, 11, 15], 9), twoSum([3, 3], 6))

function groupAnagrams(words) {
  const groups = new Map()
  for (const w of words) {
    const key = [...w].sort().join("")
    if (!groups.has(key)) groups.set(key, [])
    groups.get(key).push(w)
  }
  return [...groups.values()]
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

const counts = new Map()
for (const ch of "mississippi") counts.set(ch, (counts.get(ch) ?? 0) + 1)
console.log([...counts].sort((a, b) => b[1] - a[1]).slice(0, 2))

function balanced(expr) {
  const pairs = { ")": "(", "]": "[", "}": "{" }
  const stack = []
  for (const ch of expr) {
    if ("([{".includes(ch)) stack.push(ch)
    else if (ch in pairs && stack.pop() !== pairs[ch]) return false
  }
  return stack.length === 0
}
for (const e of ["([]{})", "([)]", "((", ""]) console.log(JSON.stringify(e).padEnd(10), balanced(e))

function nextGreater(nums) {
  // For each element, the next element to its right that is bigger (-1 if none). O(n).
  const result = new Array(nums.length).fill(-1)
  const stack = []                       // indexes whose answer is still unknown
  nums.forEach((n, i) => {
    while (stack.length && nums[stack.at(-1)] < n) result[stack.pop()] = n
    stack.push(i)
  })
  return result
}
console.log(nextGreater([2, 1, 2, 4, 3]))

function subsets(items) {
  // Backtracking: choose or skip each item
  const out = []
  const go = (i, chosen) => {
    if (i === items.length) { out.push([...chosen]); return }
    chosen.push(items[i]); go(i + 1, chosen); chosen.pop()   // take it, recurse, undo
    go(i + 1, chosen)                                        // skip it
  }
  go(0, [])
  return out
}
console.log(subsets([1, 2, 3]))

function permutations(items) {
  if (items.length <= 1) return [items]
  return items.flatMap((x, i) => permutations([...items.slice(0, i), ...items.slice(i + 1)]).map(p => [x, ...p]))
}
console.log(permutations(["a", "b", "c"]).map(p => p.join("")))

// Sorting as the first move
function mergeIntervals(intervals) {
  const iv = intervals.toSorted((a, b) => a[0] - b[0])   // by start — now overlaps are adjacent
  const merged = [iv[0]]
  for (const [start, end] of iv.slice(1)) {
    const last = merged.at(-1)
    if (start <= last[1]) last[1] = Math.max(last[1], end)
    else merged.push([start, end])
  }
  return merged
}
console.log(mergeIntervals([[5, 8], [1, 3], [2, 4], [9, 10]]))

const people = [["ada", 36, "data"], ["bob", 28, "infra"], ["cy", 36, "infra"]]
console.log(people.toSorted((a, b) => b[1] - a[1] || a[0].localeCompare(b[0])))   // age desc, then name asc
console.log(people.toSorted((a, b) => a[2].localeCompare(b[2]))[0])                 // stable: first "data" in original order

const graph = { A: ["B", "C"], B: ["D"], C: ["D", "E"], D: ["F"], E: ["F"], F: [] }

function bfsShortest(graph, start, goal) {
  // Queue + visited set. First time we reach goal is the shortest path.
  const queue = [[start]]
  const visited = new Set([start])
  let head = 0                                   // index instead of shift() — O(1) dequeue
  while (head < queue.length) {
    const path = queue[head++]
    const node = path.at(-1)
    if (node === goal) return path
    for (const next of graph[node]) {
      if (!visited.has(next)) { visited.add(next); queue.push([...path, next]) }
    }
  }
  return null
}
console.log(bfsShortest(graph, "A", "F"))

function dfsReachable(graph, start) {
  const seen = new Set(), stack = [start]
  while (stack.length) {
    const node = stack.pop()
    if (seen.has(node)) continue
    seen.add(node)
    stack.push(...graph[node])
  }
  return [...seen].sort()
}
console.log(dfsReachable(graph, "C"))

// Grid DFS: number of islands (connected 1s)
function islands(grid) {
  const rows = grid.length, cols = grid[0].length
  const seen = new Set()
  let count = 0
  for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) {
    if (grid[r][c] !== "1" || seen.has(`${r},${c}`)) continue
    count++
    const stack = [[r, c]]
    while (stack.length) {
      const [y, x] = stack.pop()
      if (y < 0 || y >= rows || x < 0 || x >= cols || grid[y][x] !== "1" || seen.has(`${y},${x}`)) continue
      seen.add(`${y},${x}`)
      stack.push([y + 1, x], [y - 1, x], [y, x + 1], [y, x - 1])
    }
  }
  return count
}
console.log(islands(["11000", "11000", "00100", "00011"]))

// DP: memoised recursion vs the exponential original
const memo = new Map()
function waysToClimb(n) {          // 1 or 2 steps at a time
  if (n <= 1) return 1
  if (!memo.has(n)) memo.set(n, waysToClimb(n - 1) + waysToClimb(n - 2))
  return memo.get(n)
}
console.log(waysToClimb(50))

// DP: bottom-up table — coin change, fewest coins
function minCoins(coins, amount) {
  const best = [0, ...Array(amount).fill(Infinity)]
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1)
  return best[amount] === Infinity ? -1 : best[amount]
}
console.log(minCoins([1, 5, 10, 25], 63), minCoins([2], 3))

// Problem: given click events { user, t } sorted by time (seconds), find users
// with 3+ clicks within any 60-second window.
//
// Contract: array of { user: string, t: number } sorted by t → sorted array of users. Empty → [].
// Brute force: for each user, every pair of clicks — O(n²).
// Pattern: group by user (hash map), then sliding window over each user's times — O(n).

function burstyUsers(events, k = 3, window = 60) {
  const byUser = new Map()
  for (const { user, t } of events) {
    if (!byUser.has(user)) byUser.set(user, [])
    byUser.get(user).push(t)
  }
  const out = []
  for (const [user, times] of byUser) {
    let left = 0
    for (let right = 0; right < times.length; right++) {
      while (times[right] - times[left] > window) left++
      if (right - left + 1 >= k) { out.push(user); break }
    }
  }
  return out.sort()
}

const events = [
  { user: "ada", t: 0 }, { user: "bob", t: 5 }, { user: "ada", t: 30 }, { user: "ada", t: 59 },
  { user: "bob", t: 100 }, { user: "cy", t: 120 }, { user: "bob", t: 130 }, { user: "bob", t: 200 },
]
console.log(burstyUsers(events))          // ada: 0,30,59 within 60 → yes. bob: 100,130,200 → 100 apart → no
console.log(burstyUsers([]))
console.log(burstyUsers(events, 2, 10))

// Problem: a log has lines "LEVEL message". Return the top-2 most frequent
// messages per level, ties broken alphabetically.
//
// Contract: string[] → { [level]: [message, count][] }. Unknown format → skip the line.
// Pattern: map of maps (a counter per level), then sort by (-count, message).

function topMessages(lines, n = 2) {
  const perLevel = new Map()
  for (const line of lines) {
    const i = line.indexOf(" ")
    if (i === -1) continue
    const level = line.slice(0, i), msg = line.slice(i + 1)
    if (!perLevel.has(level)) perLevel.set(level, new Map())
    const c = perLevel.get(level)
    c.set(msg, (c.get(msg) ?? 0) + 1)
  }
  const result = {}
  for (const [level, c] of perLevel) {
    result[level] = [...c].sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0])).slice(0, n)
  }
  return result
}

const log = ["ERROR db timeout", "INFO started", "ERROR db timeout", "ERROR disk full",
             "INFO started", "INFO done", "garbage", "ERROR auth failed", "ERROR disk full"]
for (const [level, top] of Object.entries(topMessages(log))) console.log(level, top)