Leetcode Problem 1649. Create Sorted Array through Instructions

1649. Create Sorted Array through Instructions

Leetcode Solutions

Approach: Binary Indexed Tree (BIT)

  1. Define a BIT with a size large enough to accommodate all values in instructions.
  2. Initialize a variable totalCost to store the total cost of insertions.
  3. Iterate over each element in instructions: a. Query the BIT to find the number of elements less than the current element (prefix sum). b. Query the BIT to find the number of elements greater than the current element (total sum - prefix sum up to and including the current element). c. Calculate the cost as the minimum of the two values obtained in steps a and b. d. Add the cost to totalCost. e. Update the BIT with the current element.
  4. Return totalCost modulo 10^9 + 7.
UML Thumbnail

Approach: Merge Sort

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...