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
nums.add(smaller, instructions[i]);
}
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
public void add(int index) {
add(index, 1, 0, 0, size);
}
// 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
tree.add(instructions[i]);
}
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.