Editorial: LeetCode 1649 Create Sorted Array Through Instructions
https://leetcode.com/problems/create-sorted-array-through-instructions/ from Akuna Capital
Thinking process:
The question is to find the min cost for each insertion. If we want to insert a 3 into below array, we need to find the x and y and use them to calculate the cost.
Checking the constraint, we can do this in O(NlogN) time, which leads us to some data structure which has O(logN) time for both insertion and query, like tree. Since we need to query the number of element before us or after us, this is like calculating the prefix sum of the frequency of each element like below.
We can do this by using binary indexed tree or segment tree. For me, binary indexed tree is easier to implement, so I use binary indexed tree to solve it.
Below is the code.
1class Solution {
2public:
3 vector<int> arr;
4 int high;
5 void add(int x) {
6 while (x <= high) {
7 arr[x]++;
8 x += x & (-x);
9 }
10 }
11 int q(int x) {
12 if (x == 0) return x;
13 int ret = 0;
14 while (x) {
15 ret += arr[x];
16 x -= x & (-x);
17 }
18 return ret;
19 }
20 int createSortedArray(vector<int>& instructions) {
21 high = 1e5;
22 arr.resize(high+1);
23 int N = instructions.size();
24 int sum = 0;
25 int mod = 1e9 + 7;
26 for (int i=0; i<N; i++) {
27 add(instructions[i]);
28 int left = q(instructions[i]-1);
29 int right = i + 1 - q(instructions[i]);
30 sum = (sum + min(left, right) % mod) % mod;
31 }
32 return sum;
33 }
34};