Implement an algorithm to summarize the number of items within buckets of ranges

The time complexity should be dependent on two dimensions: the size of the first array (n), and the number of buckets (m). The best we can get is O(n+m), because certainly all values of the first array must be visited, and since the output has one entry per bucket, we must also do O(m) work to produce that output.

Your code is aiming for that time complexity, but it has an issue. For instance, the following call will not produce the correct result:

summarize([9], [[1, 3], [4, 6], [7, 9]])

The issue is that your code is not good at skipping several (more than one) bucket to find the place where a value should be bucketed. Concretely, both if conditions can be false, and then nothing happens with the currently iterated value -- it is not accounted for.

Since the output has the same size as the bucket list, we could consider mapping the bucket list to the output. Then the i index becomes an auxiliary index for the first array.

Here is how the code could look:

function summarize(array, buckets) {
    let i = 0;
    return buckets.map(([start, end]) => {
        while (array[i] < start) i++;
        let j = i;
        while (array[i] <= end) i++;
        return i - j;
    });
}

// Example run
console.log(summarize([0, 10, 60, 120],[[0, 59], [60, 90]]));

Your code seems to rely on buckets being both non overlapping AND adjacent.

The code below only requires that each "bucket" array be in ascending order. As it is (with the "break" commented) it doesn't require the numbers to be in any order, and the buckets can overlap, etc.

HTH

function summarize(array, buckets) {

  const results = new Array(buckets.length).fill(0);
  for (i in array) {
    for (j in buckets) {
      if (array[i] >= buckets[j][0] && array[i] <= buckets[j][1]) {
        results[j]++;
        // break;
      }
    }
  }

  return results;
}
console.log(summarize([0, 10, 60, 120], [
  [0, 59],
  [60, 90]
]));

This doesn't require the input or buckets to be sorted and it allows the buckets to overlap:

summarize=(a,b)=>b.map(x=>a.filter(y=>y>=x[0]&&y<=x[1]).length)

Edit: The nisetama2 function in the following benchmark requires that the input and buckets are sorted and that the buckets do not overlap:

let nisetama=(a,b)=>b.map(x=>a.filter(y=>y>=x[0]&&y<=x[1]).length)

function nisetama2(a,b){
  let min=b[0][0],max=b[0][1],n=0,out=Array(b.length).fill(0)
  for(let i=0,l=a.length;i<l;i++){
    let v=a[i]
    while(v>max){if(n==b.length-1)return out;n++;min=b[n][0];max=b[n][1]}
    if(v>=min)out[n]++
  }
  return out
}

function nistetama2_for_of(a,b){
  let min=b[0][0],max=b[0][1],n=0,out=Array(b.length).fill(0)
  for(let v of a){
    while(v>max){if(n==b.length-1)return out;n++;min=b[n][0];max=b[n][1]}
    if(v>=min)out[n]++
  }
  return out
}

function OP(array, buckets) {
  let i = 0
  const results = Array.from({ length: buckets.length }, () => 0)
  for (const item of array) {
    if (item >= buckets[i][0] && item <= buckets[i][1]) results[i]++
    else if (item > buckets[i][1] && i !== buckets.length - 1) {
      if (item <= buckets[i + 1][0]) {
        results[i + 1]++
        i++
        if (i === buckets.length) break
      }
    }
  }

  return results
}

function WolfD(array, buckets) {
  const results = new Array(buckets.length).fill(0);
  for (i in array) {
    for (j in buckets) {
      if (array[i] >= buckets[j][0] && array[i] <= buckets[j][1]) {
        results[j]++;
      }
    }
  }
  return results;
}

function WolfD_let(array, buckets) {
  const results = new Array(buckets.length).fill(0);
  for (let i in array) {
    for (let j in buckets) {
      if (array[i] >= buckets[j][0] && array[i] <= buckets[j][1]) {
        results[j]++;
      }
    }
  }
  return results;
}

function trincot(array, buckets) {
    let i = 0;
    return buckets.map(([start, end]) => {
        while (array[i] < start) i++;
        let j = i;
        while (array[i] <= end) i++;
        return i - j;
    });
}

let a=Array(1e4).fill().map((_,i)=>i)
let b=Array(1e2).fill().map((_,i)=>[i*100,(i+1)*100-1])

let opt=['nisetama','nisetama2','nisetama2_for_of','OP','WolfD','WolfD_let','trincot']
opt.sort(()=>Math.random()-.5)
for(let opti of opt){
  let t1=process.hrtime.bigint()
  eval(opti+'(a,b)')
  let t2=process.hrtime.bigint()
  console.log(t2-t1+' '+opti)
}

Here's the median time of a thousand runs in ms (updated to add trincot's function):

0.43 trincot
0.67 nisetama2
3.10 nisetama2_for_of
4.03 OP
12.66 nisetama
45.32 WolfD_let
201.55 WolfD

Wolf D.'s solution became about 4 times faster when I modified it to use block-scoped variables.

In order to reduce the effect of optimizations for running the same code multiple times, I ran the benchmark like for i in {0..999};do node temp.js;done instead of running each option a thousand times inside the script.