Vultr DocsLatest Content

Create Sorted Array through Instructions

Updated on 16 May, 2025
Create Sorted Array through Instructions header image

Problem Statement

In this task, you are given an integer array called instructions. Your goal is to construct a sorted array using these values, beginning with an empty list named nums. You must insert each integer from instructions into nums sequentially from left to right.

However, every insertion carries a computational cost. This cost is determined by the minimum of two possible values:

  • The count of numbers currently in nums that are strictly less than the number currently being inserted.
  • The count of numbers currently in nums that are strictly greater than the number currently being inserted.

The mission is to compute the total cost of inserting all the integers from the instructions array into nums. Given the potential size of the number, the final answer should be returned modulo (10^9 + 7).

Examples

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.

Constraints

  • 1 <= instructions.length <= 105
  • 1 <= instructions[i] <= 105

Approach and Intuition

The straightforward approach to solve this problem involves tracking the elements in the list nums as we insert new elements while calculating costs. However, constantly calculating the count of numbers less than or greater than the current number could lead to inefficiencies, especially with large arrays.

  1. Data Structure Choice:

    • A balanced binary search tree, or a structure like a Fenwick Tree (Binary Indexed Tree) or Segment Tree, may be optimal for maintaining the sequence and efficiently counting elements.

  2. Algorithm Outline:

    • Initialize an empty data structure that supports rapid insertion and rank queries (finding the number of elements less than the given element).
    • For each element in the instructions array:
      • Calculate how many elements are less than the current element using a rank query.
      • Calculate how many elements are more by subtracting the rank from the total number of elements before insertion.
      • The cost of insertion is the minimum of these two values.
      • Perform the insertion so that the structure remains updated.
      • Accumulate the cost after making it modulo (10^9 + 7).

  3. Efficiency Considerations:

    • Both insertion and counting operations should ideally be more efficient than (O(n)), aiming for (O(\log n)) to handle constraints efficiently where the length of instructions could go up to (10^5).

By tackling the problem using a sophisticated data structure that manages the sort order and counts efficiently, the solution can handle large inputs within the constraints effectively. This strategic choice minimizes straightforward list operations, which would be computationally expensive and exceed time limits for large input sizes.

Solutions

  • C++
  • Java
  • Python
cpp 
class Arrangement {
    vector<int> lesser;
    vector<int> greater;

public:
    int computeCost(vector<int>& instructions) {
        int size = instructions.size();
        lesser.resize(size);
        greater.resize(size);
        // Utilizing raw array for operations
        int tempStore[size][2]; // for intermediate storage purposes
        long totalCost = 0;
        long modValue = 1000000007;

        int lesserInfo[size][2];
        int greaterInfo[size][2];

        for (int i = 0; i < size; i++) {
            lesserInfo[i][0] = instructions[i];
            lesserInfo[i][1] = i;
            greaterInfo[i][0] = instructions[i];
            greaterInfo[i][1] = i;
            lesser[i] = 0;
            greater[i] = 0;
        }

        detailSortLesser(lesserInfo, 0, size - 1, tempStore);
        detailSortGreater(greaterInfo, 0, size - 1, tempStore);

        for (int i = 0; i < size; i++) {
            totalCost += min(lesser[i], greater[i]);
            totalCost %= modValue;
        }
        return (int)(totalCost % modValue);
    }

    void detailSortLesser(int arr[][2], int start, int end, int tmp[][2]) {
        if (start == end) {
            return;
        }
        int middle = (start + end) / 2;
        detailSortLesser(arr, start, middle, tmp);
        detailSortLesser(arr, middle + 1, end, tmp);
        mergeLesser(arr, start, end, middle, tmp);
    }

    void mergeLesser(int arr[][2], int start, int end, int middle, int tmp[][2]) {
        int i = start;
        int j = middle + 1;
        int k = start;
        while (i <= middle && j <= end) {
            if (arr[i][0] < arr[j][0]) {
                tmp[k][0] = arr[i][0];
                tmp[k][1] = arr[i][1];
                k++;
                i++;
            } else {
                tmp[k][0] = arr[j][0];
                tmp[k][1] = arr[j][1];
                k++;
                lesser[arr[j][1]] += i - start;
                j++;
            }
        }
        while (i <= middle) {
            tmp[k][0] = arr[i][0];
            tmp[k][1] = arr[i][1];
            k++;
            i++;
        }
        while (j <= end) {
            tmp[k][0] = arr[j][0];
            tmp[k][1] = arr[j][1];
            k++;
            lesser[arr[j][1]] += i - start;
            j++;
        }
        for (i = start; i <= end; i++) {
            arr[i][0] = tmp[i][0];
            arr[i][1] = tmp[i][1];
        }
    }

    void detailSortGreater(int arr[][2], int start, int end, int tmp[][2]) {
        if (start == end) {
            return;
        }
        int middle = (start + end) / 2;
        detailSortGreater(arr, start, middle, tmp);
        detailSortGreater(arr, middle + 1, end, tmp);
        mergeGreater(arr, start, end, middle, tmp);
    }

    void mergeGreater(int arr[][2], int start, int end, int middle, int tmp[][2]) {
        int i = start;
        int j = middle + 1;
        int k = start;
        while (i <= middle && j <= end) {
            if (arr[i][0] <= arr[j][0]) {
                tmp[k][0] = arr[i][0];
                tmp[k][1] = arr[i][1];
                k++;
                i++;
            } else {
                tmp[k][0] = arr[j][0];
                tmp[k][1] = arr[j][1];
                k++;
                greater[arr[j][1]] += middle - i + 1;
                j++;
            }
        }
        while (i <= middle) {
            tmp[k][0] = arr[i][0];
            tmp[k][1] = arr[i][1];
            k++;
            i++;
        }
        while (j <= end) {
            tmp[k][0] = arr[j][0];
            tmp[k][1] = arr[j][1];
            k++;
            greater[arr[j][1]] += middle - i + 1;
            j++;
        }
        for (i = start; i <= end; i++) {
            arr[i][0] = tmp[i][0];
            arr[i][1] = tmp[i][1];
        }
    }
};

This C++ solution for creating a sorted array using provided instructions involves two main vectors, lesser and greater, that help calculate the minimal cost of sorting—a critical aspect in optimizing performance.

Below summarizes the key steps and operations:

  • Initial Preparation: Initialization of lesser and greater vectors to store temporal results for the sorting costs, and initialization of the arrays lesserInfo and greaterInfo which are used for sorting operations.

  • Sorting Operations: The code utilizes a divide-and-conquer sorting algorithm. The main functions, detailSortLesser and detailSortGreater, recursively split the array into subarrays until they reach individual elements, then merge them in a way that counts how many elements each number is less than or greater than across its half of the list.

  • Merging Process: During the merging steps (mergeLesser and mergeGreater), counts are updated for each element. In mergeLesser, the lesser counts are updated based on how many elements are encountered before merging from the other half that are larger. Similarly, in mergeGreater, counts are updated based on how many elements are smaller.

  • Cost Computation: Once the vectors are fully processed, the minor value between each element's counts in lesser and greater is used to calculate the total cost effectively combining the results of both sorted directions (lower and higher).

  • Modulo Operation: The total cost is reduced using a modulo operation with a predetermined value (modValue) to both handle large numbers and avoid integer overflow, ensuring that the result remains within manageable limits and adheres to potential problem constraints on number size.

Each function is meticulously designed to maintain efficient computation and minimize the number of operations needed to both sort the elements and calculate the minimal cost. This approach ensures that the process is both memory-efficient and fast, crucial for handling large data inputs effectively.

java 
class SortedArrayCreator {
    int[] lesserElements;
    int[] greaterElements;
    int[][] intermediateData;

    public int createSortedArray(int[] inputs) {
        int length = inputs.length;
        lesserElements = new int[length];
        greaterElements = new int[length];
        intermediateData = new int[length][];
        long totalCost = 0;
        long MODULO = 1000000007;

        int[][] ascendingData = new int[length][];
        int[][] descendingData = new int[length][];
        for (int i = 0; i < length; i++) {
            ascendingData[i] = new int[] { inputs[i], i };
            descendingData[i] = new int[] { inputs[i], i };
        }

        ascendingSort(ascendingData, 0, length - 1);
        descendingSort(descendingData, 0, length - 1);

        for (int i = 0; i < length; i++) {
            totalCost += Math.min(lesserElements[i], greaterElements[i]);
        }
        return (int) (totalCost % MODULO);
    }

    private void ascendingSort(int[][] data, int start, int end) {
        if (start == end) {
            return;
        }
        int middle = (start + end) / 2;
        ascendingSort(data, start, middle);
        ascendingSort(data, middle + 1, end);
        mergeAscending(data, start, end, middle);
    }

    private void mergeAscending(int[][] data, int start, int end, int middle) {
        int leftIndex = start;
        int rightIndex = middle + 1;
        int sortIndex = start;
        while (leftIndex <= middle && rightIndex <= end) {
            if (data[leftIndex][0] < data[rightIndex][0]) {
                intermediateData[sortIndex++] = data[leftIndex++];
            } else {
                intermediateData[sortIndex++] = data[rightIndex];
                lesserElements[data[rightIndex][1]] += leftIndex - start;
                rightIndex++;
            }
        }
        while (leftIndex <= middle) {
            intermediateData[sortIndex++] = data[leftIndex++];
        }
        while (rightIndex <= end) {
            intermediateData[sortIndex++] = data[rightIndex];
            lesserElements[data[rightIndex][1]] += leftIndex - start;
            rightIndex++;
        }
        for (int i = start; i <= end; i++) {
            data[i] = intermediateData[i];
        }
    }

    private void descendingSort(int[][] data, int start, int end) {
        if (start == end) {
            return;
        }
        int middle = (start + end) / 2;
        descendingSort(data, start, middle);
        descendingSort(data, middle + 1, end);
        mergeDescending(data, start, end, middle);
    }

    private void mergeDescending(int[][] data, int start, int end, int middle) {
        int leftIndex = start;
        int rightIndex = middle + 1;
        int sortIndex = start;
        while (leftIndex <= middle && rightIndex <= end) {
            if (data[leftIndex][0] <= data[rightIndex][0]) {
                intermediateData[sortIndex++] = data[leftIndex++];
            } else {
                intermediateData[sortIndex++] = data[rightIndex];
                greaterElements[data[rightIndex][1]] += middle - leftIndex + 1;
                rightIndex++;
            }
        }
        while (leftIndex <= middle) {
            intermediateData[sortIndex++] = data[leftIndex++];
        }
        while (rightIndex <= end) {
            intermediateData[sortIndex++] = data[rightIndex];
            greaterElements[data[rightIndex][1]] += middle - leftIndex + 1;
            rightIndex++;
        }
        for (int i = start; i <= end; i++) {
            data[i] = intermediateData[i];
        }
    }
}

The Java code provided implements a method for creating a sorted array from a given set of instructions. The aim of this method is to calculate the minimum cost of each number insertion into the sorted array, where the cost is defined by the number of elements that are either less than or greater than the number being inserted.

Key Components of the Solution:

  • Arrays to Track Costs and Indices:

    • lesserElements[] and greaterElements[] arrays are used to store, respectively, the number of lesser and greater elements compared to each element at a specific index.
    • intermediateData[][] is utilized as a temporary storage during the merging process in sorting.

  • Sorting Mechanisms:

    • The sorting of array elements is conducted in both ascending and descending order, using a custom implementation of merge sort (ascendingSort and descendingSort functions).
    • The mergeAscending and mergeDescending functions handle the merging process of the sorted halves, updating the lesserElements and greaterElements with the appropriate counts during the merge.

  • Cost Calculation:

    • After sorting, the method iterates through the elements and calculates the total cost based on the lesser of the values from lesserElements[i] and greaterElements[i] for each i, which represents the optimal insert position cost for each number.

  • Modular Arithmetic:

    • To handle large numbers resulting from the cost calculation, modular arithmetic is employed using a MODULO value of 1000000007 to return the result as required by possibly large constraints.

Execution Steps:

  1. Initialization of arrays and variables needed to store intermediary and result data.
  2. Sorting the input data in both ascending and descending orders.
  3. Merging the sorted data while simultaneously counting the crucial lesser and greater elements during the insertion process.
  4. Calculating the total cost for inserting all numbers with minimal disturbances to the existing order of the array.
  5. Finally, returning the cost modulo 1000000007 to handle potential integer overflow and adhere to problem constraints.

Overall, this solution efficiently computes the envisioned result by leveraging advanced sorting and merging strategies, coupled with optimized data storage mechanics. This approach ensures that both time complexity and space usage are managed effectively.

python 
class Solution:
    def calculateCost(self, instructions: List[int]) -> int:
        length = len(instructions)
        left_elements_smaller = [0] * length
        right_elements_bigger = [0] * length
        sortable = [0] * length

        def perform_sort_smaller(data, start, end):
            if start == end:
                return
            middle = (start + end) // 2
            perform_sort_smaller(data, start, middle)
            perform_sort_smaller(data, middle + 1, end)
            helper_merge_smaller(data, start, end, middle)

        def helper_merge_smaller(data, start, end, middle):
            idx1 = start
            idx2 = middle + 1
            sort_idx = start
            while idx1 <= middle and idx2 <= end:
                if data[idx1][0] < data[idx2][0]:
                    sortable[sort_idx] = data[idx1]
                    sort_idx += 1
                    idx1 += 1
                else:
                    sortable[sort_idx] = data[idx2]
                    left_elements_smaller[data[idx2][1]] += idx1 - start
                    sort_idx += 1
                    idx2 += 1

            while idx1 <= middle:
                sortable[sort_idx] = data[idx1]
                sort_idx += 1
                idx1 += 1
            while idx2 <= end:
                sortable[sort_idx] = data[idx2]
                left_elements_smaller[data[idx2][1]] += idx1 - start
                sort_idx += 1
                idx2 += 1
            for i in range(start, end + 1):
                data[i] = sortable[i]

        def perform_sort_larger(data, start, end):
            if start == end:
                return
            middle = (start + end) // 2
            perform_sort_larger(data, start, middle)
            perform_sort_larger(data, middle + 1, end)
            helper_merge_larger(data, start, end, middle)

        def helper_merge_larger(data, start, end, middle):
            idx1 = start
            idx2 = middle + 1
            sort_idx = start
            while idx1 <= middle and idx2 <= end:
                if data[idx1][0] <= data[idx2][0]:
                    sortable[sort_idx] = data[idx1]
                    sort_idx += 1
                    idx1 += 1
                else:
                    sortable[sort_idx] = data[idx2]
                    right_elements_bigger[data[idx2][1]] += middle - idx1 + 1
                    sort_idx += 1
                    idx2 += 1

            while idx1 <= middle:
                sortable[sort_idx] = data[idx1]
                sort_idx += 1
                idx1 += 1
            while idx2 <= end:
                sortable[sort_idx] = data[idx2]
                right_elements_bigger[data[idx2][1]] += middle - idx1 + 1
                sort_idx += 1
                idx2 += 1
            for i in range(start, end + 1):
                data[i] = sortable[i]

        MODULO = 10**9 + 7
        total_cost = 0

        indexed_data_smaller = [[value, index] for index, value in enumerate(instructions)]
        indexed_data_larger = [[value, index] for index, value in enumerate(instructions)]

        perform_sort_smaller(indexed_data_smaller, 0, length - 1)
        perform_sort_larger(indexed_data_larger, 0, length - 1)

        for index in range(length):
            total_cost += min(left_elements_smaller[index], right_elements_bigger[index])
        return total_cost % MODULO

Create a sorted array with minimal costs by following a structured procedure in Python. The provided code outlines an optimization technique that leverages merge sort principles to optimally place each element with respect to the instructions specified.

  • Start with an array of instructions and prepare to track elements by two metrics: smaller elements to the left and larger elements to the right.
  • Define functions to perform merge sort. Separate functions are used for sorting elements lesser than the current element (perform_sort_smaller) and for those greater (perform_sort_larger).
  • Implement helper functions helper_merge_smaller and helper_merge_larger to merge segments during the sort. Additionally, these helpers calculate the cost contributions of placing each element by counting conflicts during the merge.
  • Utilize a modular arithmetic constant MODULO = 10**9 + 7 to ensure that the resulting cost remains within bounds, suitable for large numbers.
  • Calculate the final cost iteratively. For each element, the minimal cost is determined by comparing counts of smaller left elements and larger right elements, and the smaller count is added to the total cost.
  • The calculateCost method incorporates sorting and calculating the costs in two passes which are efficiently managed through indexing.

Ensure to carefully analyze and adapt functions according to your unique application needs, maintaining clean encapsulation and division of functionality for clarity and maintainability. This approach not only ensures efficient execution but also maintains scalability and adaptability of the code.

Comments

No comments yet.