g1601_1700.s1649_create_sorted_array_through_instructions.Solution

public class Solution extends Object

1649 - Create Sorted Array through Instructions.Hard Given an integer array <code>instructions</code>, you are asked to create a sorted array from the elements in <code>instructions</code>. You start with an empty container <code>nums</code>. For each element from left to right in <code>instructions</code>, insert it into <code>nums</code>. The cost of each insertion is the minimum of the following: <ul> <li>The number of elements currently in <code>nums</code> that are strictly less than <code>instructions[i]</code>.</li> <li>The number of elements currently in <code>nums</code> that are strictly greater than <code>instructions[i]</code>.</li> </ul> For example, if inserting element <code>3</code> into <code>nums = [1,2,3,5]</code>, the cost of insertion is <code>min(2, 1)</code> (elements <code>1</code> and <code>2</code> are less than <code>3</code>, element <code>5</code> is greater than <code>3</code>) and <code>nums</code> will become <code>[1,2,3,3,5]</code>. Return the total cost to insert all elements from <code>instructions</code> into <code>nums</code>. Since the answer may be large, return it modulo <code>109 + 7</code> 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: <ul> <li><code>1 <= instructions.length <= 105</code></li> <li><code>1 <= instructions[i] <= 105</code></li> </ul>

Constructor Summary

Constructors

Constructor

Description

Solution()
Method Summary

Modifier and Type

Method

Description

int

createSortedArray(int[] instructions)

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- Solution
  
  public Solution()
Method Details
- createSortedArray
  
  public int createSortedArray(int[] instructions)

Class Solution

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

Solution

Method Details

createSortedArray