Create Sorted Array through Instructions - Practice Coding Problems

Create Sorted Array through Instructions - Problem

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set Hard

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

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: instructions = [1,5,6,2]

› Output: 1

💡 Note: Insert 1: cost=0. Insert 5: smaller=[1], larger=[], cost=0. Insert 6: smaller=[1,5], larger=[], cost=0. Insert 2: smaller=[1], larger=[5,6], cost=min(1,2)=1. Total=1.

Example 2 — Multiple Costs

$ Input: instructions = [1,2,3,6,5,4]

› Output: 3

💡 Note: Each insertion incurs the minimum of smaller/larger elements count. Cost accumulates as: 0+0+0+0+1+2=3.

Example 3 — Duplicates

$ Input: instructions = [1,3,3,3,2,4,2,1,2]

› Output: 4

💡 Note: When inserting duplicates, they don't count as strictly smaller or larger, minimizing costs in some cases.

Constraints

1 ≤ instructions.length ≤ 10⁵
1 ≤ instructions[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of instructions to insert: [1,5,6,2]

Process

Insert each element, calculate min(smaller, larger) as cost

Output

Return total accumulated insertion cost

Key Takeaway

🎯 Key Insight: The cost is always the minimum of smaller or larger elements, favoring insertions at array ends

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that insertion cost is always the minimum of elements smaller or larger than current element. The optimal approach uses Binary Indexed Tree with coordinate compression to achieve O(n log n) time by efficiently counting elements in ranges. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n²)	O(n)	For each element, maintain sorted array and count smaller/larger elements
Coordinate Compression + Binary Indexed Tree	O(n log n)	O(n)	Use coordinate compression and BIT to efficiently count smaller/larger elements
Binary Search Optimization	O(n²)	O(n)	Use binary search to find insertion position and count elements efficiently

Brute Force - Linear Search — Algorithm Steps

Step 1: For each instruction, find insertion position in sorted array
Step 2: Count elements smaller and larger than current element
Step 3: Add minimum cost and insert element to maintain sorted order

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert First

Add first element with cost 0

Count & Insert

For each new element, count smaller/larger

Accumulate Cost

Add minimum cost to total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* instructions, int size) {
    const int MOD = 1000000007;
    int* nums = (int*)malloc(size * sizeof(int));
    int numsSize = 0;
    long long totalCost = 0;
    
    for (int i = 0; i < size; i++) {
        int num = instructions[i];
        int smaller = 0;
        int larger = 0;
        
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] < num) smaller++;
            else if (nums[j] > num) larger++;
        }
        
        int cost = (smaller < larger) ? smaller : larger;
        totalCost = (totalCost + cost) % MOD;
        
        nums[numsSize++] = num;
        qsort(nums, numsSize, sizeof(int), compare);
    }
    
    free(nums);
    return (int)totalCost;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int instructions[100000];
    int size = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            instructions[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(instructions, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n elements, we scan up to n elements to find position and count

⚠ Quadratic Growth

Space Complexity

O(n)

Extra array to maintain sorted elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler