// Пример: сумма двух чисел = target
function twoSum(nums: number[], target: number): number[] {
  let i = 0,
    j = nums.length - 1
  while (i < j) {
    const sum = nums[i] + nums[j]
    if (sum === target) return [i, j]
    else if (sum < target) i++
    else j--
  }
  return []
}

// Пример: максимальная сумма подмассива длины k
function maxSum(nums: number[], k: number): number {
  let sum = nums.slice(0, k).reduce((a, b) => a + b, 0)
  let max = sum
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]
    max = Math.max(max, sum)
  }
  return max
}

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

function buildPrefix(nums: number[]): number[] {
  const prefix = [0]
  for (const n of nums) prefix.push(prefix.at(-1)! + n)
  return prefix
}
// сумма [i, j] = prefix[j+1] - prefix[i]

// Пример: два числа дают target (неотсортированный массив)
function twoSumHash(nums: number[], target: number): number[] {
  const map = new Map<number, number>()
  for (let i = 0; i < nums.length; i++) {
    const comp = target - nums[i]
    if (map.has(comp)) return [map.get(comp)!, i]
    map.set(nums[i], i)
  }
  return []
}

// Пример: следующий больший элемент
function nextGreater(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1)
  const stack: number[] = [] // хранит индексы
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[i] > nums[stack.at(-1)!]) {
      result[stack.pop()!] = nums[i]
    }
    stack.push(i)
  }
  return result
}

function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set([start])
  const queue = [start]
  const order: number[] = []
  while (queue.length) {
    const node = queue.shift()!
    order.push(node)
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }
  return order
}

function dfs(graph: Map<number, number[]>, node: number, visited = new Set<number>()): void {
  visited.add(node)
  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited)
  }
}

// Пример: все подмножества
function subsets(nums: number[]): number[][] {
  const result: number[][] = []
  function bt(start: number, current: number[]) {
    result.push([...current])
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i])
      bt(i + 1, current)
      current.pop() // откат
    }
  }
  bt(0, [])
  return result
}

// Пример: монеты (coin change)
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

// Мини-heap вручную (min-heap через массив)
class MinHeap {
  private h: number[] = []
  push(val: number) {
    this.h.push(val)
    this.h.sort((a, b) => a - b) // упрощённо; для O(log n) — sift up
  }
  pop(): number {
    return this.h.shift()!
  }
  peek(): number {
    return this.h[0]
  }
  size(): number {
    return this.h.length
  }
}

// Пример: есть ли цикл
function hasCycle(head: ListNode | null): boolean {
  let slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}