Learning Journal

1/31/2024

Number of Equal Numbers Blocks -- 3rd attempt

Tags: algorithms leetcode divide_and_conquer

/**
 * Definition for BigArray.
 * class BigArray {
 *     constructor(elements: number[]);
 *     public at(index: number): number;
 *     public size(): number;
 * }
 */

function countBlocks(nums:BigArray |null) :number {
    let curP = 0, numBlocks = 0;

    while(curP < nums.size()) {
        const nextI = getNextI(nums, curP);
        curP = nextI;
        numBlocks++;
    }

    return numBlocks;
}

function getNextI(nums:BigArray, curI:number) {
    let lo = curI, hi = nums.size() -1;
    const curVal = nums.at(curI);

    while(lo <= hi) {
        const midI = Math.floor((lo + hi)/2);

        const midVal = nums.at(midI);

        if(midVal !== curVal) {
            hi = midI - 1;
        }
        else {
            lo = midI + 1;
        }
    }

    return hi + 1;
}/**
 * Definition for BigArray.
 * class BigArray {
 *     constructor(elements: number[]);
 *     public at(index: number): number;
 *     public size(): number;
 * }
 */

function countBlocks(nums:BigArray |null) :number {
    let curP = 0, numBlocks = 0;

    while(curP < nums.size()) {
        const nextI = getNextI(nums, curP);
        curP = nextI;
        numBlocks++;
    }

    return numBlocks;
}

function getNextI(nums:BigArray, curI:number) {
    let lo = curI, hi = nums.size() -1;
    const curVal = nums.at(curI);

    while(lo <= hi) {
        const midI = Math.floor((lo + hi)/2);

        const midVal = nums.at(midI);

        if(midVal !== curVal) {
            hi = midI - 1;
        }
        else {
            lo = midI + 1;
        }
    }

    return hi + 1;
}

This is my third attempt at solving the problem Number of Equal Numbers Block.

Let me try to explain why the getNextI function returns hi + 1.

The while loop only stops when lo > hi but lo and hi only move inside the if-else statement. It's either lo moves to midI + 1 or hi moves to midI - 1.

What is special about midI? midI can only be greater or equal to l and can only be less or equal to hi.

So, if the if clause is executed, lo remains the same, in order for hi to be less than lo, midI must be equal to lo at the previous iteration. But, midI can not be equal to lo because in order for the if clause to be executed, midVal !== curVal.

So, if the else clause is executed, hi remains the same. In order for lo to be greater than hi, midI must be equal to hi.

When will midI be equal to hi? Well, midI is equal to hi when lo === midI === hi, which means all of them point to the same element. And I don't know by some magic, this element is the last element of the current block, so we move hi one more step to the right to make it mark the first element of the next block.**