Arrays

// ===== The model =====
// Contiguous block of memory holding elements of the same type (in low-level langs).
// In JS / Python they are dynamic arrays under the hood with some overhead.
// Random access in O(1); insertion/deletion in the MIDDLE is O(n).

// ===== Creating + accessing =====
const xs = [1, 2, 3, 4, 5];
xs[0]                           // 1 — O(1)
xs.length                       // 5
xs[xs.length - 1]               // last element
xs.at(-1)                       // also last (modern)

// ===== Iteration patterns =====
for (let i = 0; i < xs.length; i++) { /* index */ }
for (const x of xs)              { /* value */ }
xs.forEach((x, i) => { /* both */ });

// Reverse:
for (let i = xs.length - 1; i >= 0; i--) { /* ... */ }

// ===== Slicing (does NOT modify the original) =====
xs.slice(1, 3)                  // [2, 3]
xs.slice(-2)                    // last 2
[...xs]                         // shallow copy

// ===== Mutation (modifies in place) =====
xs.push(6);                     // [1,2,3,4,5,6]    O(1) amortised
xs.pop();                       // removes last     O(1)
xs.unshift(0);                  // [0,1,2,3,4,5]    O(n)
xs.shift();                     // removes first    O(n)
xs.splice(2, 1, 99);            // remove + insert

xs.reverse();
xs.sort((a, b) => a - b);       // ALWAYS pass a comparator for numbers

// ===== Higher-order helpers =====
const doubled = xs.map(x => x * 2);
const evens = xs.filter(x => x % 2 === 0);
const sum = xs.reduce((acc, x) => acc + x, 0);
const found = xs.find(x => x > 3);
const idx = xs.findIndex(x => x > 3);
const has = xs.includes(3);

// ===== Two-pointer pattern =====
// Reverse in place:
function reverse(arr) {
  let i = 0, j = arr.length - 1;
  while (i < j) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; j--; }
}

// Two-sum on sorted array:
function pairSum(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo < hi) {
    const s = sorted[lo] + sorted[hi];
    if (s === target) return [lo, hi];
    s < target ? lo++ : hi--;
  }
  return null;
}

// ===== Sliding window =====
// Max sum of any subarray of size k:
function maxSum(xs, k) {
  let s = 0;
  for (let i = 0; i < k; i++) s += xs[i];
  let best = s;
  for (let i = k; i < xs.length; i++) {
    s += xs[i] - xs[i - k];
    if (s > best) best = s;
  }
  return best;
}

// ===== Prefix sums =====
function prefixSum(xs) {
  const p = [0];
  for (const x of xs) p.push(p[p.length - 1] + x);
  return p;
}
// Range sum [l, r] = p[r+1] - p[l]   in O(1) after O(n) build

// ===== 2D arrays =====
const grid = Array.from({ length: 3 }, () => Array(4).fill(0));
grid[1][2] = 9;

// ===== Patterns to internalise =====
// - Pick the operation -> pick the structure (mid-insert? maybe LinkedList)
// - Sort + sweep beats O(n^2) pairwise
// - Two-pointer / sliding window for ordered or contiguous problems
// - Prefix sums for range queries
// - In-place ops to save memory when allowed

// ===== Pitfalls =====
// - JS .sort() lexical by default; supply a comparator for numbers
// - Mutating arrays you got from a function (clone first with [...arr])
// - .splice in a hot loop -> O(n) per call
// - Accessing arr.length inside the loop condition can be optimised but rarely matters

// Random access in O(1). Insert/delete at front in O(n).
const a = [1, 2, 3];
a.push(4);   // O(1) amortised
a.unshift(0); // O(n)