Minimum Absolute Difference Queries LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<bitset<101>> tree;
4
  vector<int> minDifference(vector<int> &nums, vector<vector<int>> &queries) {
5
    int n = nums.size();
6

7
    tree = vector<bitset<101>>(4 * (n + 1) + 1);
8
    buildtree(1, 0, n - 1, nums);
9

10
    vector<int> ans;
11
    for (auto &e : queries) {
12
      auto finalOnesRepresentations = query(1, 0, n - 1, e[0], e[1]);
13

14
      // find the first 1
15
      int i = 0;
16
      while (i < 101 and finalOnesRepresentations[i] != 1) {
17
        i++;
18
      }
19

20
      int gap = INT_MAX;
21
      int prev = i;
22
      i++;
23
      // find the minimum gap
24
      for (; i < 101; i++) {
25
        if (finalOnesRepresentations[i] == 1) {
26
          gap = min(gap, i - prev);
27
          prev = i;
28
        }
29
      }
30
      ans.push_back(gap == INT_MAX ? -1 : gap);
31
    }
32
    return ans;
33
  }
34

35
  bitset<101> query(int index, int s, int e, int qs, int qe) {
36
    if (s > e) return bitset<101>();
37
    if (e < qs || s > qe) return bitset<101>();
38
    if (qs <= s and e <= qe) return tree[index];
39

40
    int mid = (s + e) / 2;
41
    auto left = query(index * 2, s, mid, qs, qe);
42
    auto right = query(index * 2 + 1, mid + 1, e, qs, qe);
43
    return left | right;
44
  }
45

46
  void buildtree(int index, int s, int e, vector<int> &a) {
47
    if (s > e) return;
48

49
    if (s == e) {
50
      bitset<101> b;
51
      b[a[s]] = 1;
52
      tree[index] = b;
53
      return;
54
    }
55

56
    int mid = (s + e) / 2;
57
    buildtree(index * 2, s, mid, a);
58
    buildtree(index * 2 + 1, mid + 1, e, a);
59
    tree[index] = tree[index * 2] | tree[index * 2 + 1];
60
  }
61
};