Find the Champion in an Array Game

Given a distinct-integer array arr and an integer k, simulate a game where the first two elements compete in each round. The larger value wins, stays at index 0, and the smaller one is moved to the end. The game ends as soon as any value wins k consecutive rounds; that value is the champion.

Examples

• arr = [2,1,3,5,4,6,7], k = 2 → 5
• arr = [3,2,1], k = 10 → 3
• arr = [1,9,8,2,3,7,6,4,5], k = 7 → 9
• arr = [1,11,22,33,44,55,66,77,88,99], k = 1e9 → 99

Key Insight

Physically rotating the array is unnecessary. Once the current maximum is encountered, it will defeat every remaining element in order, so we only need to count consecutive victories until k is reached.

function champion(nums, k) {
    let streak = 0, cur = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        if (cur > nums[i]) {
            ++streak;
        } else {
            cur = nums[i];
            streak = 1;
        }
        if (streak === k) break;
    }
    return cur;
}

Minimum Adjacent Swaps to Make a Binary Grid Upper-Triangular

An n×n binary matrix is valid if every cell above the main diagonal is 0. You may swap any two adjacent rows. Return the minimum number of swaps required, or -1 if impossible.

Examples

• [[0,0,1],[1,1,0],[1,0,0]] → 3
• [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] → -1
• [[1,0,0],[1,1,0],[1,1,1]] → 0

Approach

1. For each row, count the number of trailing zeros (suffix zeros).
2. Row i must have atleast n-1-i trailing zeros.
3. Greedily bubble the closest qualifying row upward, summing the swaps.

function minSwaps(grid) {
    const n = grid.length;
    const zeros = [];

    // Compute suffix zeros for every row
    for (let r = 0; r < n; ++r) {
        let z = 0;
        for (let c = n - 1; c >= 0 && grid[r][c] === 0; --c) ++z;
        zeros.push(z);
    }

    let swaps = 0;

    for (let target = 0; target < n - 1; ++target) {
        const need = n - 1 - target;
        let pick = target;

        // Locate the first row below that satisfies the requirement
        while (pick < n && zeros[pick] < need) ++pick;
        if (pick === n) return -1;

        // Bubble this row up to position `target`
        while (pick > target) {
            [zeros[pick], zeros[pick - 1]] = [zeros[pick - 1], zeros[pick]];
            --pick;
            ++swaps;
        }
    }
    return swaps;
}