// interview patterns 
// Queue — JS has no built-in queue; array shift() is O(n), fine for interview-scale input
const queue: number[] = [];
queue.push(1);        // enqueue
queue.shift();          // dequeue

// Min-heap / priority queue — no built-in. Two options in an interview:
// 1) Say explicitly: "TS has no built-in heap, I'd normally reach for a library
//    like `heap-js`; here's how I'd implement one manually if needed."
// 2) For small inputs, sort an array repeatedly (state the O(n log n) per op cost).

// 2D array init — classic mistake: Array(n).fill([]) shares ONE array reference
const grid = Array.from({ length: rows }, () => Array(cols).fill(0)); // correct
// const bad = new Array(rows).fill(new Array(cols).fill(0)); // WRONG — all rows share memory

// type narrowing
function process(input: string | number) {
  if (typeof input === "string") {
    return input.toUpperCase();   // TS knows it's a string here
  }
  return input.toFixed(2);         // TS knows it's a number here
}

// Array.isArray, instanceof, and 'in' also narrow types
if (Array.isArray(val)) { /* val is treated as an array */ }
if (node instanceof TreeNode) { /* ... */ }

Two Sum

Pattern: Hash map | O(n) time, O(n) space

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement)!, i];
    seen.set(nums[i], i);
  }
  return [];
}

Valid Parentheses

Pattern: Stack | O(n) time, O(n) space

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

  for (const c of s) {
    if (c === "(" || c === "[" || c === "{") {
      stack.push(c);
    } else {
      if (stack.pop() !== pairs[c]) return false;
    }
  }

  return stack.length === 0;
}

Contains Duplicate

Pattern: Set | O(n) time, O(n) space

function containsDuplicate(nums: number[]): boolean {
  return new Set(nums).size !== nums.length;
}

Maximum Subarray (Kadane's Algorithm)

Pattern: Dynamic programming (running optimum) | O(n) time, O(1) space

function maxSubArray(nums: number[]): number {
  let maxSoFar = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSoFar = Math.max(maxSoFar, currentSum);
  }

  return maxSoFar;
}

Reverse Linked List

Pattern: Pointer manipulation | O(n) time, O(1) space

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  return prev;
}

Merge Intervals

Pattern: Sort + greedy sweep | O(n log n) time, O(n) space