This page explains Java solution to problem Create Sorted Array through Instructions
using Binary Indexed Tree
algorithm.
Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums
. For each element from left to right in instructions, insert it into nums
. The cost of each insertion is the minimum of the following:
nums
that are strictly less than instructions[i]
.nums
that are strictly greater than instructions[i]
.
For example, if inserting element 3
into nums = [1,2,3,5]
, the cost of insertion is min(2, 1)
(elements 1
and 2
are less than 3
, element 5
is greater than 3
) and nums
will become [1,2,3,3,5]
.
Example 2:Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.
Example 3:Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.
Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.
package com.vc.hard;
class CreateSortedArrayThroughInstructions {
private int[] count;
private int limit = (int)1e5 + 1;
private int MOD = (int)1e9 + 7;
public int createSortedArray(int[] instructions) {
int totalCost = 0;
this.count = new int[limit];
for(int i = 0; i < instructions.length; i++) {
int smallerNumberCount = getCount(instructions[i] - 1);
int greaterNumberCount = i - getCount(instructions[i]);
totalCost = (totalCost + Math.min(smallerNumberCount, greaterNumberCount)) % MOD;
updateCount(instructions[i]);
}
return totalCost;
}
private void updateCount(int number) {
while(number < limit) {
count[number]++;
number += number & -number;
}
}
private int getCount(int number) {
int res = 0;
while(number > 0) {
res += count[number];
number -= number & -number;
}
return res;
}
}
O(N log M) Where
N is total number of instructions in an input array
M is maximum value in an instructions input array, in our case it is 1e5 + 1
O(M) Where
M is maximum value in an instructions input array, in our case it is 1e5 + 1