Number of Flowers in Full Bloom LeetCode solution in JavaScript

1
/**
2
 * @param {number[][]} flowers
3
 * @param {number[]} persons
4
 * @return {number[]}
5
 */
6
var fullBloomFlowers = function (flowers, persons) {
7
  // *** IDEATION *** //
8
  // key observation:
9
  // total number of flowers see on day i =
10
  // number of flowers has already bloomed so far on day i - number of flowers already ended ("died") prior to day i
11

12
  // find number of flowers already bloomed on day i
13
  // each flower has a start day
14
  // start array = [1, 3, 9, 4] for example
15
  // on day 8, there are 3 flowers bloomed:
16
  // equivalent to find the number of elements in the "start" array which is less than or equal to 8
17

18
  // find number of flowers already ended on day i
19
  // each flower has an end day
20
  // end array = [6, 7, 12, 13] for example
21
  // on day 8, there are 2 flowers already ended:
22
  // equivalent to find the number of elements in the "end" array which is less than 8
23
  // equivalent to find the number of elements in the "end" array which is less than or equal to 7
24

25
  // both process above can be solved efficiently with binary search on a sorted array
26
  // hence we need to first build 2 array "start" and "end" and sorted it
27
  // then apply the formula at the beginning to return the required answer
28

29
  // *** IMPLEMENTATION *** //
30
  // step 1: build the "start" and "end" array
31
  let start = [];
32
  let end = [];
33

34
  for (let i = 0; i < flowers.length; i++) {
35
    start[i] = flowers[i][0];
36
    end[i] = flowers[i][1];
37
  }
38

39
  // step 2: sort the "start" and "end" array
40
  start.sort((a, b) => a - b);
41
  end.sort((a, b) => a - b);
42

43
  // step 3: apply the observation formula using a binarySearch function
44
  let res = [];
45
  for (let j = 0; j < persons.length; j++) {
46
    res[j] =
47
      binarySearch(start, persons[j]) - binarySearch(end, persons[j] - 1);
48
  }
49
  return res;
50

51
  // step 4: implement the binarySearch function (variant from standard binarySearch)
52
  function binarySearch(array, k) {
53
    // array is sorted;
54
    // obj is to find the number of elements in array which is less than or equal to "k"
55
    let left = 0;
56
    let right = array.length - 1;
57
    let index = -1;
58

59
    while (left <= right) {
60
      let mid = left + Math.floor((right - left) / 2);
61
      if (k < array[mid]) {
62
        right = mid - 1;
63
      } else {
64
        index = Math.max(index, mid); // record the index whenever k >= array[mid]
65
        left = mid + 1;
66
      }
67
    }
68

69
    // all elements with in array from position '0' to position 'index' will be less than or equal to k
70
    return index + 1;
71
  }
72
};