1649. Create Sorted Array through Instructions #

Problem #

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^9 + 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 <= 105
• 1 <= instructions[i] <= 105

Problem Summary #

You are given an integer array instructions. You need to create a sorted array according to the elements in instructions. Initially, you have an empty array nums. You need to traverse the elements in instructions from left to right and insert them into the nums array one by one. The cost of each insertion operation is the smaller of the following two values:

• The number of elements in nums that are strictly less than instructions[i].
• The number of elements in nums that are strictly greater than instructions[i].

For example, if you want to insert 3 into nums = [1,2,3,5], then the cost of the insertion operation is min(2, 1) (elements 1 and 2 are less than 3, and element 5 is greater than 3), and after insertion nums becomes [1,2,3,3,5]. Please return the total minimum cost after inserting all elements in instructions into nums one by one. Since the answer may be large, return it modulo 10^9 + 7.

Solution Ideas #

• Given an array, insert its elements from the beginning into another empty array. Before each insertion, accumulate the cost value cost = min(strictly less than, strictly greater than). Finally output the accumulated value.
• Although this problem is Hard, after reading it you can determine that it is a template problem. It can be solved with a segment tree or a Binary Indexed Tree. Here is a brief explanation of the segment tree approach: first sort the array to be inserted to obtain the overall interval. Each loop performs 4 steps: 2 query operations to obtain strictlyLessThan and strictlyGreaterThan respectively, then compare them and accumulate the smaller value, and the last step is update.
• Since the data given in the problem is relatively large, remember to discretize before building the segment tree. The core code for this problem is no more than 10 lines; the rest is all template code. See the code for the specific implementation.

Code #

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

// Solution 1: Binary Indexed Tree
func createSortedArray(instructions []int) int {
	bit, res := template.BinaryIndexedTree{}, 0
	bit.Init(100001)
	for i, v := range instructions {
		less := bit.Query(v - 1)
		greater := i - bit.Query(v)
		res = (res + min(less, greater)) % (1e9 + 7)
		bit.Add(v, 1)
	}
	return res
}

// Solution 2: Segment Tree
func createSortedArray1(instructions []int) int {
	if len(instructions) == 0 {
		return 0
	}
	st, res, mod := template.SegmentCountTree{}, 0, 1000000007
	numsMap, numsArray, tmpArray := discretization1649(instructions)
	// Initialize the segment tree; values in the nodes are all set to 0, i.e., counts are 0
	st.Init(tmpArray, func(i, j int) int {
		return 0
	})
	for i := 0; i < len(instructions); i++ {
		strictlyLessThan := st.Query(0, numsMap[instructions[i]]-1)
		strictlyGreaterThan := st.Query(numsMap[instructions[i]]+1, numsArray[len(numsArray)-1])
		res = (res + min(strictlyLessThan, strictlyGreaterThan)) % mod
		st.UpdateCount(numsMap[instructions[i]])
	}
	return res
}

func discretization1649(instructions []int) (map[int]int, []int, []int) {
	tmpArray, numsArray, numsMap := []int{}, []int{}, map[int]int{}
	for i := 0; i < len(instructions); i++ {
		numsMap[instructions[i]] = instructions[i]
	}
	for _, v := range numsMap {
		numsArray = append(numsArray, v)
	}
	sort.Ints(numsArray)
	for i, num := range numsArray {
		numsMap[num] = i
	}
	for i := range numsArray {
		tmpArray = append(tmpArray, i)
	}
	return numsMap, numsArray, tmpArray
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}