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:
nums that are strictly less than instructions[i].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 109 + 7
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 <= 1051 <= instructions[i] <= 105This approach uses a Binary Indexed Tree (BIT) data structure to efficiently count the number of elements less than and greater than the current element during the insertion process.
We maintain a BIT to store the frequency of each element from the instructions array. For each element, we calculate the cost as the minimum of the count of elements that are less than it and the count of elements that are greater than it that have been inserted so far. We use BIT to efficiently calculate prefix sums, which helps in calculating these counts.
The C implementation uses a Binary Indexed Tree (BIT) to keep track of element counts. The update function updates the tree, and the query function retrieves prefix sums. These are used to count how many elements are less than or greater than the current element, allowing for efficient insertion cost calculation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), where n is the number of instructions. The operations of update and query on the BIT are O(log n).
Space Complexity: O(n), to store the BIT.
This approach employs a Segment Tree to perform range query operations to efficiently count the number of elements less than and greater than the current element during insertion. The Segment Tree helps maintain the frequency of elements within a range and can provide range sum in logarithmic time, allowing for quick calculations of the insertion cost.
The C implementation uses a Segment Tree to efficiently count elements in a range for insertion cost calculation. The update function alters the Segment Tree to reflect changes in element frequency, while query retrieves summations of elements over a range.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), where n is the number of instructions. The Segment Tree operations take O(log n).
Space Complexity: O(n), to store the Segment Tree.
| Approach | Complexity |
|---|---|
| Approach 1: Binary Indexed Tree (Fenwick Tree) Solution | Time Complexity: O(n log n), where n is the number of instructions. The operations of update and query on the BIT are O(log n). Space Complexity: O(n), to store the BIT. |
| Approach 2: Segment Tree Solution | Time Complexity: O(n log n), where n is the number of instructions. The Segment Tree operations take O(log n). Space Complexity: O(n), to store the Segment Tree. |
Merge Sorted Array - Leetcode 88 - Python • NeetCode • 276,790 views views
Watch 9 more video solutions →Practice Create Sorted Array through Instructions with our built-in code editor and test cases.
Practice on FleetCode