Learning Journal

2/1/2024

Number of Equal Numbers Blocks --- 4th 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()) {
        curP = getStartI(nums, curP);
        numBlocks++;        
    }

    return numBlocks;
}

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

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

        const midVal = nums.at(midP);

        if(midVal !== curVal) {
            hi = midP - 1;
        }
        else {
            lo = midP + 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()) {
        curP = getStartI(nums, curP);
        numBlocks++;        
    }

    return numBlocks;
}

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

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

        const midVal = nums.at(midP);

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

    return hi  + 1;
}

This is my 4th attempt at solving this leetcode problem. I just recognized something interesting.

The basic idea of binary search is to look at the middle element to see if it is the thing that you are looking for. It it is, return that element. It it is not, compare that element to the element you are looking for to see if the unknown element is on the right or left side of the array, then continue to do the same thing to that side of the array until the upper bound and lower bound limits converge.

In this case, what we are looking for is an element that is neither equal nor different from the current element. You can never find that element, it does not exist. So, the loop will always stop in the middle, at the line between the two blocks. Then, by some miracle, the hi pointer moves 1 step further to the current block. That is why we need to return hi + 1.