Miscellaneous Algorithms

// Find element appearing > n/2 times (guaranteed to exist)
function majorityElement(nums) {
    let candidate = nums[0], count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) { candidate = nums[i]; count = 1; }
        else if (nums[i] === candidate) count++;
        else count--;
    }
    return candidate; // guaranteed majority exists
}

// Find all elements appearing > n/3 times
function majorityElementII(nums) {
    let cand1 = 0, cand2 = 1, cnt1 = 0, cnt2 = 0;
    for (const n of nums) {
        if (n === cand1) cnt1++;
        else if (n === cand2) cnt2++;
        else if (cnt1 === 0) { cand1 = n; cnt1 = 1; }
        else if (cnt2 === 0) { cand2 = n; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    // Verify (candidates aren't guaranteed to be majority)
    cnt1 = cnt2 = 0;
    for (const n of nums) {
        if (n === cand1) cnt1++;
        else if (n === cand2) cnt2++;
    }
    const res = [];
    if (cnt1 > nums.length / 3) res.push(cand1);
    if (cnt2 > nums.length / 3) res.push(cand2);
    return res;
}

// 2×3 board: find min moves to reach [[1,2,3],[4,5,0]]
function slidingPuzzle(board) {
    const target = '123450';
    const start = board.flat().join('');
    if (start === target) return 0;

    // 2D neighbors in flattened index for a 2×3 grid
    const neighbors = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]];

    const visited = new Set([start]);
    const queue = [[start, 0]];

    while (queue.length) {
        const [state, steps] = queue.shift();
        const zero = state.indexOf('0');
        for (const neighbor of neighbors[zero]) {
            const arr = state.split('');
            [arr[zero], arr[neighbor]] = [arr[neighbor], arr[zero]];
            const next = arr.join('');
            if (next === target) return steps + 1;
            if (!visited.has(next)) { visited.add(next); queue.push([next, steps+1]); }
        }
    }
    return -1;
}

// General pattern for small state-space BFS:
// 1. Encode state as string/number
// 2. BFS with visited set
// 3. Generate all valid next states

function isSolvable(board) {
    const n = board.length;
    const flat = board.flat();
    let inversions = 0;
    let blankRow = 0;

    // Count inversions
    for (let i = 0; i < flat.length; i++) {
        if (flat[i] === 0) { blankRow = Math.floor(i / n); continue; }
        for (let j = i + 1; j < flat.length; j++) {
            if (flat[j] !== 0 && flat[i] > flat[j]) inversions++;
        }
    }

    if (n % 2 === 1) {
        return inversions % 2 === 0; // odd width: inversions must be even
    } else {
        // even width: inversions + blank row from bottom must be odd
        const blankFromBottom = n - 1 - blankRow;
        return (inversions + blankFromBottom) % 2 === 1;
    }
}

// Pick 1 random item from stream of unknown length
// Each item has equal 1/n probability
class ReservoirSampler {
    constructor() { this.reservoir = null; this.count = 0; }
    add(item) {
        this.count++;
        // Accept with probability 1/count
        if (Math.random() * this.count < 1) this.reservoir = item;
    }
}

// Pick k items: maintain reservoir of size k
// For each new item i (0-indexed): replace random position in reservoir
// with probability k/(i+1)
function reservoirSample(stream, k) {
    const res = stream.slice(0, k);
    for (let i = k; i < stream.length; i++) {
        const j = Math.floor(Math.random() * (i + 1));
        if (j < k) res[j] = stream[i];
    }
    return res;
}