// ─── Array fundamentals ───────────────────────────────────────

const arr = [10, 20, 30, 40, 50];

// O(1) — Direct index access (base_addr + i * size)
console.log(arr[2]);          // 30 — always instant
console.log(arr.at(-1));      // 50 — negative index (ES2022)

// O(n) — Linear search (unsorted array)
const idx = arr.indexOf(30);  // 2  — scans left-to-right
const has = arr.includes(30); // true

// O(1) amortized — Push to end (dynamic resize doubles capacity)
arr.push(60);                 // [10, 20, 30, 40, 50, 60]

// O(n) — Insert at beginning (shifts all elements right)
arr.unshift(5);               // [5, 10, 20, 30, 40, 50, 60]

// O(1) — Remove from end
arr.pop();                    // [5, 10, 20, 30, 40, 50]

// O(n) — Remove from beginning (shifts all elements left)
arr.shift();                  // [10, 20, 30, 40, 50]

// O(n) — Insert/delete in middle via splice
arr.splice(2, 0, 99);         // [10, 20, 99, 30, 40, 50] — insert at index 2
arr.splice(2, 1);             // [10, 20, 30, 40, 50]      — delete at index 2

// ─── Two-pointer technique (avoid O(n²) with O(n) + array) ───

// O(n) — Reverse in-place using two pointers
function reverseInPlace(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]]; // Swap
    lo++; hi--;
  }
  return arr;
}

// O(n) — Remove duplicates from sorted array in-place (O(1) extra space)
function deduplicateSorted(arr) {
  let write = 1;
  for (let read = 1; read < arr.length; read++) {
    if (arr[read] !== arr[read - 1]) arr[write++] = arr[read];
  }
  return arr.slice(0, write);
}

// ─── Sliding window (O(n) over O(n²) nested loops) ─────────────

// O(n) — Max sum subarray of length k
function maxSumSubarray(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // Slide: add new, remove old — O(1) per step
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}