Create Sorted Array through Instructions

Create Sorted Array through Instructions

What is this problem about?

In the Create Sorted Array through Instructions interview question, you are given an array instructions. You build a new sorted array one by one. For each element, the "cost" of inserting it is the minimum of:

1. The number of elements already in the array strictly less than the current element.
2. The number of elements already in the array strictly greater than the current element. The goal is to calculate the total cost of inserting all elements, returned modulo $10^9 + 7$.

Why is this asked in interviews?

Google and Akuna Capital use this Hard coding problem to test your knowledge of advanced data structures for range queries. A naive approach (sorting or using a simple list) takes O(N^2), which is too slow for $N=10^5$. It evaluates your ability to use Binary Indexed Trees (Fenwick Trees) or Segment Trees to perform point updates and prefix sums in O(log M) time, where M is the maximum value in the input.

Algorithmic pattern used

This problem uses Binary Indexed Tree (BIT) or Segment Tree.

1. Initialize a BIT to store the frequencies of numbers.
2. For each number x in instructions:
   • Use the BIT to get the number of elements less than x: query(x - 1).
   • Use the BIT to get the number of elements less than or equal to x: query(x).
   • Total elements so far is i.
   • cost_less = query(x - 1).
   • cost_greater = i - query(x).
   • total_cost += min(cost_less, cost_greater).
   • Update the BIT: update(x, 1).

Example explanation

instructions = [1, 5, 6, 2]

1. Insert 1: cost = min(0, 0) = 0. BIT: {1: 1}.
2. Insert 5: cost = min(1, 0) = 0. BIT: {1: 1, 5: 1}.
3. Insert 6: cost = min(2, 0) = 0. BIT: {1: 1, 5: 1, 6: 1}.
4. Insert 2:
   • Elements < 2: one (1).
   • Elements > 2: two (5, 6).
   • cost = min(1, 2) = 1. Total cost: 1.

Common mistakes candidates make

• Integer Overflow: Forgetting to apply modulo $10^9 + 7$ to the final sum.
• Range vs Value: Confusion between the number of instructions (N) and the range of values (M). The BIT should be sized based on the maximum value in the array.
• O(N log N) with wrong constant: Using a balanced BST which might be slower in some languages compared to a Fenwick tree.

Interview preparation tip

Fenwick Trees are much easier to implement during an interview than Segment Trees. Practice the update and query functions until you can write them in under 2 minutes.