# Create Sorted Array Through Instructions in Java

Given an array of integers called instructions. The task is to construct a sorted array from these elements. We have an empty container called nums. We will process each element of instructions from left to right. When inserting an element into nums, the cost of insertion is determined by the number of elements already in nums that are either strictly less than or strictly greater than the current element. We should minimize this cost at each insertion.

Example 1:

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 2:

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.

Example 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.

## Approach 1: Using Brute Force

The Brute Force approach involves iterating through the instructions array and processing each element one by one. For each element in the instructions array, the code determines the number of elements smaller and larger than the current element that already exists in the sorted array constructed so far. It then calculates the cost of insertion based on these counts and updates the total cost accordingly.

### Algorithm

Step 1: Initialize a variable cost to 0 to keep track of the total cost.

Step 2: Initialize an empty list nums to store the elements.

Step 3: Iterate through each element in the instructions array.

Step 4: For each element, iterate through the elements already in nums to count the number of elements smaller and larger than the current element.

Step 5: Calculate the cost of insertion as the minimum of the smaller and larger counts.

Step 6: Increment the total cost by the calculated cost.

Step 7: Insert the current element from the instructions into nums at the position determined by the smaller count.

Step 8: Repeat the steps for each element in the instructions.

Step 9: Return the total cost.

Filename: SortedArrayCostUsingBruteForce.java

```import java.util.ArrayList;

import java.util.List;

public class SortedArrayCostUsingBruteForce {

// Method to create a sorted array and calculate the total cost of insertion

public static int createSortedArray(int[] instructions) {

int cost = 0; // Initialize the total cost to 0

List nums = new ArrayList<>(); // Create an empty list to store elements

// Iterate through each element in the instructions array

for (int i = 0; i < instructions.length; i++) {

int smaller = 0, larger = 0; // Initialize counters for elements smaller and larger than the current element

// Iterate through each element already in nums

for (int num : nums) {

if (num < instructions[i]) // If the element is smaller than the current element in instructions

smaller++; // Increment the smaller counter

else if (num > instructions[i]) // If the element is larger than the current element in instructions

larger++; // Increment the larger counter

}

// Calculate the cost of insertion as the minimum of smaller and larger counters

cost = (cost + Math.min(smaller, larger)) % 1000000007;

// Insert the current element from instructions into nums at the position determined by the smaller counter

}

return cost; // Return the total cost

}

// Main method to test the createSortedArray method

public static void main(String[] args) {

int[] instructions = {1, 5, 6, 2};

System.out.println("Total cost: " + createSortedArray(instructions));

}

}```

Output

`Total cost: 1`

Time Complexity: The time complexity of an algorithm is O(n^2), where n is the number of elements in the instructions array. This is because, for each element in instructions, we can iterate through all the elements already in nums to count the smaller and larger elements.

Space Complexity: The space complexity of an algorithm is O(n), where n is the number of elements in the instructions array. This is because we use an additional list nums to store the elements.

## Approach 2: Using Binary Indexed Tree

The Binary Indexed Tree is also known as Fenwick Tree. This approach is to efficiently calculate the number of elements smaller and larger than the current element during each insertion.

### Algorithm

Step 1: Initialize a binary indexed tree (BIT) with size equal to the maximum element in the instructions array.

Step 2: Iterate through each element in the instructions array.

Step 3: For each element, query the BIT to find the number of elements smaller than the current element and the number of elements larger than the current element.

Step 4: Calculate the cost of insertion as the minimum of the smaller and larger counts.

Step 5: Update the BIT to reflect the insertion of the current element.

Step 6: Accumulate the total cost of insertion.

Step 7: Repeat steps for each element in the instructions array.

Step 8: Return the total cost.

Filename: SortedArrayCostUsingBIT.java

```import java.util.Arrays;

public class SortedArrayCostUsingBIT {

// Method to create a sorted array and calculate the total cost of insertion

public static int createSortedArray(int[] instructions) {

int mod = (int)1e9 + 7; // Modulus value

int cost = 0; // Initialize the total cost to 0

int maxValue = Arrays.stream(instructions).max().getAsInt(); // Find the maximum element in the instructions array

int[] bit = new int[maxValue + 1]; // Create a Binary Indexed Tree (BIT) with size equal to the maximum element + 1

// Iterate through each element in the instructions array

for (int i = 0; i < instructions.length; i++) {

// Query the BIT to find the number of elements smaller than the current element

int smaller = query(bit, instructions[i] - 1);

// Calculate the number of elements larger than the current element by subtracting the count of smaller elements from the current index

int larger = i - query(bit, instructions[i]);

// Calculate the cost of insertion as the minimum of smaller and larger counts

cost = (cost + Math.min(smaller, larger)) % mod;

// Update the BIT to reflect the insertion of the current element

update(bit, instructions[i], 1);

}

return cost; // Return the total cost

}

// Method to query the BIT and calculate the sum of elements from index 1 to index

public static int query(int[] bit, int index) {

int sum = 0; // Initialize sum to 0

// Traverse the BIT upwards from the given index and add the values to sum

while (index > 0) {

sum = (sum + bit[index]) % 1000000007; // Add the value at the current index to sum

index -= index & (-index); // Move to the parent node in the BIT

}

return sum; // Return the sum

}

// Method to update the BIT with the given index and value

public static void update(int[] bit, int index, int value) {

// Traverse the BIT upwards from the given index and update the values

while (index < bit.length) {

bit[index] = (bit[index] + value) % 1000000007; // Update the value at the current index

index += index & (-index); // Move to the next node in the BIT

}

}

// Main method to test the createSortedArray method

public static void main(String[] args) {

int[] instructions = {1, 5, 6, 2};

System.out.println("Total cost: " + createSortedArray(instructions));

}

}```

Output

`Total cost: 1`

Time Complexity: The time complexity of an algorithm is O(n * log(m)), where n is the number of elements in the instructions array and m is the maximum element in the instructions array. This is because each query and update operation on the BIT takes O(log(m)) time, and there is n such operations.

Space Complexity: The space complexity of an algorithm is O(m), where m is the maximum element in the instructions array. This is because the BIT has a size equal to the maximum element in the instructions array.

## Approach 3: Segment Tree

Segment Trees are data structures that allow for efficient querying and updating of intervals. We can use a Segment Tree to keep track of the count of elements smaller than the current element and larger than the current element.

### Algorithm

Step 1: Create a segment tree to store counts of smaller elements.

Step 2: Iterate through each element in the instructions array.

Step 3: Query the segment tree to find the count of smaller elements.

Step 4: Calculate the count of elements larger than the current element.

Step 5: Calculate the cost of insertion as the minimum of smaller and larger counts.

Step 6: Add the current element to the segment tree.

Step 7: Repeat steps for each element in the instructions array.

Step 8: Return the total cost.

Filename: SortedArrayCostUsingSegmentTree.java

```import java.util.Arrays;

public class SortedArrayCostUsingSegmentTree {

// Nested class representing the Segment Tree data structure

static class SegmentTree {

int[] smaller; // Array to store counts of smaller elements

int size; // Size of the segment tree

// Constructor to initialize the segment tree with size n

public SegmentTree(int n) {

size = 1;

// Find the nearest power of 2 greater than or equal to n

while (size < n) size *= 2;

// Initialize arrays to store counts of smaller elements

smaller = new int[2 * size];

}

// Method to add an element to the segment tree

}

// Recursive helper method to update counts in the segment tree

private void add(int index, int val, int node, int left, int right) {

if (right - left == 1) {

smaller[node]++; // Increment count of smaller elements

return;

}

int mid = left + (right - left) / 2;

if (index < mid)

add(index, val, 2 * node + 1, left, mid);

else

add(index, val, 2 * node + 2, mid, right);

// Update the count of smaller elements in the current node

smaller[node] = smaller[2 * node + 1] + smaller[2 * node + 2];

}

// Method to query the segment tree for counts in a range

public int query(int left, int right, int node, int nodeLeft, int nodeRight) {

if (nodeRight <= left || nodeLeft >= right) // No overlap

return 0;

if (nodeLeft >= left && nodeRight <= right) // Fully covered

return smaller[node];

int mid = nodeLeft + (nodeRight - nodeLeft) / 2;

// Recursively query the left and right children

return query(left, right, 2 * node + 1, nodeLeft, mid) +

query(left, right, 2 * node + 2, mid, nodeRight);

}

}

// Method to calculate the total cost of insertion into a sorted array

public static int createSortedArray(int[] instructions) {

int mod = (int)1e9 + 7;

int cost = 0; // Initialize the total cost

// Find the maximum element in the instructions array

int maxValue = Arrays.stream(instructions).max().getAsInt();

// Initialize a segment tree with size equal to the maximum element + 1

SegmentTree tree = new SegmentTree(maxValue + 1);

// Iterate through each element in the instructions array

for (int i = 0; i < instructions.length; i++) {

// Query the segment tree to find the count of smaller elements

int smaller = tree.query(0, instructions[i], 0, 0, tree.size);

// Calculate the count of elements larger than the current element

int larger = i - smaller;

// Calculate the cost of insertion as the minimum of smaller and larger counts

cost = (cost + Math.min(smaller, larger)) % mod;

// Add the current element to the segment tree

}

return cost; // Return the total cost

}

// Main method to test the createSortedArray method

public static void main(String[] args) {

int[] instructions = {1, 5, 6, 2};

System.out.println("Total cost: " + createSortedArray(instructions));

}

}```

Output

`Total cost: 1`

Time Complexity: The time complexity of an algorithm is O(n * log(m)), where n is the number of elements in the instructions array and m is the maximum element in the instructions array. This is because each query and update operation on the segment tree takes O(log(m)) time, and there are n such operations.

Space Complexity: The space complexity of an algorithm is O(m), where m is the maximum element in the instructions array. This is because the segment tree has a size equal to the maximum element in the instructions array.