Create Sorted Array through Instructions

This page explains Java solution to problem Create Sorted Array through Instructions using Binary Indexed Tree algorithm.

Problem Statement

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:

• The number of elements currently in nums that are strictly less than instructions[i].
• The number of elements currently in 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].

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.

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.

Solution

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;
    }
}

Time Complexity

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 1e⁵ + 1

Space Complexity

O(M) Where
M is maximum value in an instructions input array, in our case it is 1e⁵ + 1