Create Sorted Array through Instructions LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> seg;
4

5
  int query(int index, int low, int high, int l, int r) {
6
    if (low >= l && high <= r) {
7
      return seg[index];
8
    }
9
    if (high < l || low > r) return 0;
10

11
    int mid = (low + high) / 2;
12
    int left = query(2 * index + 1, low, mid, l, r);
13
    int right = query(2 * index + 2, mid + 1, high, l, r);
14
    return right + left;
15
  }
16

17
  void update(int index, int low, int high, int pos) {
18
    if (low == high) {
19
      seg[index]++;
20
      return;
21
    } else {
22
      int mid = (low + high) / 2;
23
      if (pos <= mid) {
24
        update(2 * index + 1, low, mid, pos);
25
      } else {
26
        update(2 * index + 2, mid + 1, high, pos);
27
      }
28
      seg[index] = seg[2 * index + 1] + seg[2 * index + 2];
29
    }
30
  }
31

32
  int createSortedArray(vector<int> &instructions) {
33
    // using 100001 as 1e5 is the max element value
34
    seg.resize(4 * 100001, 0);
35
    int mod = 1e9 + 7;
36
    int ans = 0;
37
    for (int i = 0; i < instructions.size(); i++) {
38
      int mi = query(0, 0, 100001, 0,
39
                     instructions[i] - 1); // number of elements smaller than instruction[i]
40
      int mx = query(0, 0, 100001, instructions[i] + 1,
41
                     100001); // number of elements greater than instruction[i]
42
      update(0, 0, 100001, instructions[i]);
43
      ans = (ans + min(mi, mx)) % mod;
44
    }
45
    return ans;
46

47
    /*TLE approch using STL
48
    // 50/65 cases passed
49
   int m=instructions.size();
50
   vector<int>a;
51
   int mod=1e9+7;
52
   int ans=0;
53
   int mxe=INT_MIN;
54
   unordered_map<int,int>um;
55
   for(auto x:instructions)
56
   {
57
       int xx=lower_bound(a.begin(),a.end(),x)-a.begin();
58
       int n=a.size();
59
       um[x]++;
60
       mxe=max(mxe,x);
61
       if(n==0)
62
       {
63
           a.push_back(x);
64

65
       }
66
       else
67
       {
68
           a.insert(a.begin()+xx,x);
69

70
           int mi=xx;
71
           int m=a.size();
72
           ans=(ans+min(mi,m-mi-um[x]))%mod;
73

74
       }
75
   }
76

77
   return ans;*/
78
  }
79
};