LeetCode 1649: Create Sorted Array through Instructions
Problem Description
Explanation
To solve this problem, we can use a Binary Indexed Tree (BIT) also known as Fenwick Tree. We iterate over the instructions array, and for each element, we update the BIT to count how many elements are smaller than the current element and how many are larger. This information helps us calculate the cost of inserting the current element into the sorted array. We then update the BIT with the current element.
The total cost is the sum of the cost for each element. We return this sum modulo 10^9 + 7 as required.
Time Complexity:
- Building the BIT: O(n log n)
- Calculating the total cost: O(n log n) Overall: O(n log n)
Space Complexity: O(n) for the Binary Indexed Tree
Solutions
class Solution {
public int createSortedArray(int[] instructions) {
int mod = 1000000007;
int n = instructions.length;
int[] count = new int[100001]; // the maximum value of an element in instructions
FenwickTree tree = new FenwickTree(100001);
long cost = 0;
for (int i = 0; i < n; i++) {
int less = tree.query(instructions[i] - 1);
int greater = i - tree.query(instructions[i]);
cost += Math.min(less, greater);
cost %= mod;
tree.update(instructions[i], 1);
}
return (int) cost;
}
class FenwickTree {
int[] tree;
int n;
public FenwickTree(int n) {
this.n = n;
this.tree = new int[n + 1];
}
public void update(int i, int delta) {
while (i <= n) {
tree[i] += delta;
i += i & -i;
}
}
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & -i;
}
return sum;
}
}
}Loading editor...