// Пример: сумма двух чисел = 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;
}