GeeksforGeeks-Solution/src/Count X in Range of a Sorted Array/Code/solution.js at main · withaarzoo/GeeksforGeeks-Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
  firstOccurrence(arr, l, r, x) {
    let ans = -1;
    while (l <= r) {
      let mid = Math.floor(l + (r - l) / 2);
      if (arr[mid] === x) {
        ans = mid;
        r = mid - 1;
      } else if (arr[mid] < x) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return ans;
  }

  lastOccurrence(arr, l, r, x) {
    let ans = -1;
    while (l <= r) {
      let mid = Math.floor(l + (r - l) / 2);
      if (arr[mid] === x) {
        ans = mid;
        l = mid + 1;
      } else if (arr[mid] < x) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return ans;
  }

  countXInRange(arr, queries) {
    let result = [];

    for (let q of queries) {
      let [l, r, x] = q;

      let first = this.firstOccurrence(arr, l, r, x);
      if (first === -1) {
        result.push(0);
        continue;
      }

      let last = this.lastOccurrence(arr, l, r, x);
      result.push(last - first + 1);
    }

    return result;
  }
}