Learning Journal

1/30/2024

Number of Equal Numbers Blocks -- 2nd 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 curI = 0, numBlocks = 0;
     const max = nums.size();

     while(curI < max) {
         const nextI = getNextI(nums, curI);
         curI = nextI;
         numBlocks++;
     }

    return numBlocks;
 }

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

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

         const midVal = nums.at(midI);

         if(midVal !== val) {
             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 curI = 0, numBlocks = 0;
     const max = nums.size();

     while(curI < max) {
         const nextI = getNextI(nums, curI);
         curI = nextI;
         numBlocks++;
     }

    return numBlocks;
 }

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

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

         const midVal = nums.at(midI);

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

     }

     return hi + 1;
 }

This is my second attempt at solving the Number of Equal Numbers Blocks problem. Here are some lessons I learned this time:

Basically, what all divide and conquer algorithms do involve using a mid-point to divide the problem into two halves; if something that needs to be done is in the first half, move the upper bound pointer to mid; if it is in the second half, move the lower bound pointer to the mid. After this step, the array/problem becomes half the original one. Recursively solve the problem until it reduces to the size of 1. Then, that is the thing you're looking for.
The loop ends when low pointer and high pointer cross.
In the last iteration of the while loop in the getNextI function, lo === hi, if midVal === val, the lo pointer moves to past the midpoint, but the hi pointer remains the same. Now, hi pointer points to the last element of the current block. If midVal !== val, hi pointer moves to the left 1 unit and becomes the last element of the current block. Either way, hi pointer always points to the last element of the current block. Thus, we return hi + 1, which is the first element of the next block.