// Auxiliary space O(1) — only a few variables, no extra arrays
function sumInPlace(arr) {
  let total = 0;   // one variable — O(1) aux space
  for (const x of arr) total += x;
  return total;
}
// Input arr takes O(n) space, but we don't count that.
// Aux space = O(1).

// Auxiliary space O(n) — creates a new array proportional to input
function doubled(arr) {
  const result = [];              // new array of size n
  for (const x of arr) result.push(x * 2);
  return result;                  // O(n) aux space
}

// Auxiliary space O(n) — hash map stores up to n entries
function twoSum(nums, target) {
  const seen = new Map();         // up to n entries
  for (let i = 0; i < nums.length; i++) {
    const comp = target - nums[i];
    if (seen.has(comp)) return [seen.get(comp), i];
    seen.set(nums[i], i);
  }
  return [];
}

// O(n) stack space — n frames deep for input n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  // factorial(1000) creates 1000 stack frames
  // factorial(100000) → stack overflow in most JS engines!
}

// O(log n) stack space — halves problem each call
function binarySearch(arr, target, lo = 0, hi = arr.length - 1) {
  if (lo > hi) return -1;
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearch(arr, target, mid + 1, hi);
  return binarySearch(arr, target, lo, mid - 1);
  // max depth = log₂(n), e.g. for n=1,000,000 → only ~20 frames
}

// O(1) stack space — iterative version uses no recursion
function binarySearchIter(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  // Each call to slice() creates a NEW array — O(n) total across one level
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];   // temporary buffer — O(n) at the final merge step
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Space analysis:
// - Each level of recursion creates arrays summing to O(n) total
// - Recursion depth = O(log n) → O(log n) stack frames
// - Temporary merge arrays dominate: O(n) auxiliary space
// Total: O(n) space

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const pivot = partition(arr, lo, hi);  // in-place swapping, O(1) extra space
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];  // swap in place
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

// Space analysis:
// - No new arrays created (in-place swaps) → O(1) per call
// - Average case: balanced splits → recursion depth = O(log n)
// - Worst case: sorted array with bad pivot → depth = O(n) → O(n) stack space!
// - With randomized pivot: O(log n) stack space with high probability

// In-place array reversal: O(1) aux space
function reverseInPlace(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}
// Uses only 2 pointer variables — O(1) aux space

// NOT in-place (creates new array): O(n) aux space
function reverseNew(arr) {
  return arr.slice().reverse();  // slice() copies entire array
}

// In-place Dutch National Flag (3-way partition): O(1) aux space
function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; }
    else if (nums[mid] === 1) { mid++; }
    else { [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; }
  }
}

// O(n) space — DFS on a balanced binary tree visits all n nodes
// Maximum stack depth = tree height = O(log n) for balanced, O(n) for skewed
function dfs(node) {
  if (!node) return 0;
  return 1 + Math.max(dfs(node.left), dfs(node.right));
}
// Balanced tree (n nodes): O(log n) stack frames at any one time
// Linked-list-shaped tree: O(n) stack frames → potential stack overflow

// O(n) space — memoization table stores n results
function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}
// Stack: O(n) deep (first call goes down to fib(0))
// Memo: O(n) entries
// Total: O(n) aux space

// O(1) space — bottom-up DP avoids recursion and only needs 2 variables
function fibDP(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}