Sponsored
Sponsored
This approach uses a Binary Indexed Tree (BIT) data structure to efficiently count the number of elements less than and greater than the current element during the insertion process.
We maintain a BIT to store the frequency of each element from the instructions array. For each element, we calculate the cost as the minimum of the count of elements that are less than it and the count of elements that are greater than it that have been inserted so far. We use BIT to efficiently calculate prefix sums, which helps in calculating these counts.
Time Complexity: O(n log n), where n is the number of instructions. The operations of update and query on the BIT are O(log n).
Space Complexity: O(n), to store the BIT.
1#include <stdio.h>
2#define MAX 100001
3#define MOD 1000000007
4
5int BIT[MAX] =
The C implementation uses a Binary Indexed Tree (BIT) to keep track of element counts. The update function updates the tree, and the query function retrieves prefix sums. These are used to count how many elements are less than or greater than the current element, allowing for efficient insertion cost calculation.
This approach employs a Segment Tree to perform range query operations to efficiently count the number of elements less than and greater than the current element during insertion. The Segment Tree helps maintain the frequency of elements within a range and can provide range sum in logarithmic time, allowing for quick calculations of the insertion cost.
Time Complexity: O(n log n), where n is the number of instructions. The Segment Tree operations take O(log n).
Space Complexity: O(n), to store the Segment Tree.
class CreateSortedArraySegmentTree {
private const int MAX = 100001;
private const int MOD = 1000000007;
private int[] segTree = new int[4 * MAX];
private void Update(int node, int start, int end, int idx, int val) {
if (start == end) {
segTree[node] += val;
} else {
int mid = (start + end) / 2;
int leftChild = 2 * node + 1;
int rightChild = 2 * node + 2;
if (idx <= mid) {
Update(leftChild, start, mid, idx, val);
} else {
Update(rightChild, mid + 1, end, idx, val);
}
segTree[node] = segTree[leftChild] + segTree[rightChild];
}
}
private int Query(int node, int start, int end, int L, int R) {
if (start > R || end < L) {
return 0;
}
if (start >= L && end <= R) {
return segTree[node];
}
int mid = (start + end) / 2;
int leftChild = 2 * node + 1;
int rightChild = 2 * node + 2;
int p1 = Query(leftChild, start, mid, L, R);
int p2 = Query(rightChild, mid + 1, end, L, R);
return p1 + p2;
}
public int CreateSortedArray(int[] instructions) {
Array.Clear(segTree, 0, segTree.Length);
long cost = 0;
for (int i = 0; i < instructions.Length; i++) {
int left = Query(0, 0, MAX - 1, 0, instructions[i] - 1);
int right = i - Query(0, 0, MAX - 1, 0, instructions[i]);
cost = (cost + Math.Min(left, right)) % MOD;
Update(0, 0, MAX - 1, instructions[i], 1);
}
return (int) cost;
}
static void Main(string[] args) {
int[] instructions = {1, 5, 6, 2};
CreateSortedArraySegmentTree solution = new CreateSortedArraySegmentTree();
Console.WriteLine(solution.CreateSortedArray(instructions));
}
}C# implementation manages the state of the Segment Tree through class methods that handle element updates and query summations to compute insertion costs while implementing a entirely self-contained solution.