Binary Indexed Tree
Segment Tree
Array
Binary Search
Divide and Conquer
Ordered Set
Merge Sort
Description
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 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 <= 105
1 <= instructions[i] <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class BinaryIndexedTree :
def __init__ ( self , n ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
def update ( self , x : int , v : int ):
while x <= self . n :
self . c [ x ] += v
x += x & - x
def query ( self , x : int ) -> int :
s = 0
while x :
s += self . c [ x ]
x -= x & - x
return s
class Solution :
def createSortedArray ( self , instructions : List [ int ]) -> int :
m = max ( instructions )
tree = BinaryIndexedTree ( m )
ans = 0
mod = 10 ** 9 + 7
for i , x in enumerate ( instructions ):
cost = min ( tree . query ( x - 1 ), i - tree . query ( x ))
ans += cost
tree . update ( x , 1 )
return ans % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
this . c = new int [ n + 1 ] ;
}
public void update ( int x , int v ) {
while ( x <= n ) {
c [ x ] += v ;
x += x & - x ;
}
}
public int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ] ;
x -= x & - x ;
}
return s ;
}
}
class Solution {
public int createSortedArray ( int [] instructions ) {
int m = 0 ;
for ( int x : instructions ) {
m = Math . max ( m , x );
}
BinaryIndexedTree tree = new BinaryIndexedTree ( m );
int ans = 0 ;
final int mod = ( int ) 1e9 + 7 ;
for ( int i = 0 ; i < instructions . length ; ++ i ) {
int x = instructions [ i ] ;
int cost = Math . min ( tree . query ( x - 1 ), i - tree . query ( x ));
ans = ( ans + cost ) % mod ;
tree . update ( x , 1 );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class BinaryIndexedTree {
public :
BinaryIndexedTree ( int _n )
: n ( _n )
, c ( _n + 1 ) {}
void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += x & - x ;
}
}
int query ( int x ) {
int s = 0 ;
while ( x ) {
s += c [ x ];
x -= x & - x ;
}
return s ;
}
private :
int n ;
vector < int > c ;
};
class Solution {
public :
int createSortedArray ( vector < int >& instructions ) {
int m = * max_element ( instructions . begin (), instructions . end ());
BinaryIndexedTree tree ( m );
const int mod = 1e9 + 7 ;
int ans = 0 ;
for ( int i = 0 ; i < instructions . size (); ++ i ) {
int x = instructions [ i ];
int cost = min ( tree . query ( x - 1 ), i - tree . query ( x ));
ans = ( ans + cost ) % mod ;
tree . update ( x , 1 );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 type BinaryIndexedTree struct {
n int
c [] int
}
func newBinaryIndexedTree ( n int ) * BinaryIndexedTree {
c := make ([] int , n + 1 )
return & BinaryIndexedTree { n , c }
}
func ( this * BinaryIndexedTree ) update ( x , delta int ) {
for x <= this . n {
this . c [ x ] += delta
x += x & - x
}
}
func ( this * BinaryIndexedTree ) query ( x int ) int {
s := 0
for x > 0 {
s += this . c [ x ]
x -= x & - x
}
return s
}
func createSortedArray ( instructions [] int ) ( ans int ) {
m := slices . Max ( instructions )
tree := newBinaryIndexedTree ( m )
const mod = 1e9 + 7
for i , x := range instructions {
cost := min ( tree . query ( x - 1 ), i - tree . query ( x ))
ans = ( ans + cost ) % mod
tree . update ( x , 1 )
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 class BinaryIndexedTree {
private n : number ;
private c : number [];
constructor ( n : number ) {
this . n = n ;
this . c = new Array ( n + 1 ). fill ( 0 );
}
public update ( x : number , v : number ) : void {
while ( x <= this . n ) {
this . c [ x ] += v ;
x += x & - x ;
}
}
public query ( x : number ) : number {
let s = 0 ;
while ( x > 0 ) {
s += this . c [ x ];
x -= x & - x ;
}
return s ;
}
}
function createSortedArray ( instructions : number []) : number {
const m = Math . max (... instructions );
const tree = new BinaryIndexedTree ( m );
let ans = 0 ;
const mod = 10 ** 9 + 7 ;
for ( let i = 0 ; i < instructions . length ; ++ i ) {
const x = instructions [ i ];
const cost = Math . min ( tree . query ( x - 1 ), i - tree . query ( x ));
ans = ( ans + cost ) % mod ;
tree . update ( x , 1 );
}
return ans ;
}
Solution 2
Python3 Java C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 class Node :
def __init__ ( self ):
self . l = 0
self . r = 0
self . v = 0
class SegmentTree :
def __init__ ( self , n ):
self . tr = [ Node () for _ in range ( 4 * n )]
self . build ( 1 , 1 , n )
def build ( self , u , l , r ):
self . tr [ u ] . l = l
self . tr [ u ] . r = r
if l == r :
return
mid = ( l + r ) >> 1
self . build ( u << 1 , l , mid )
self . build ( u << 1 | 1 , mid + 1 , r )
def modify ( self , u , x , v ):
if self . tr [ u ] . l == x and self . tr [ u ] . r == x :
self . tr [ u ] . v += v
return
mid = ( self . tr [ u ] . l + self . tr [ u ] . r ) >> 1
if x <= mid :
self . modify ( u << 1 , x , v )
else :
self . modify ( u << 1 | 1 , x , v )
self . pushup ( u )
def pushup ( self , u ):
self . tr [ u ] . v = self . tr [ u << 1 ] . v + self . tr [ u << 1 | 1 ] . v
def query ( self , u , l , r ):
if self . tr [ u ] . l >= l and self . tr [ u ] . r <= r :
return self . tr [ u ] . v
mid = ( self . tr [ u ] . l + self . tr [ u ] . r ) >> 1
v = 0
if l <= mid :
v = self . query ( u << 1 , l , r )
if r > mid :
v += self . query ( u << 1 | 1 , l , r )
return v
class Solution :
def createSortedArray ( self , instructions : List [ int ]) -> int :
n = max ( instructions )
tree = SegmentTree ( n )
ans = 0
for num in instructions :
a = tree . query ( 1 , 1 , num - 1 )
b = tree . query ( 1 , 1 , n ) - tree . query ( 1 , 1 , num )
ans += min ( a , b )
tree . modify ( 1 , num , 1 )
return ans % int (( 1e9 + 7 ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 class Solution {
public int createSortedArray ( int [] instructions ) {
int n = 100010 ;
int mod = ( int ) 1e9 + 7 ;
SegmentTree tree = new SegmentTree ( n );
int ans = 0 ;
for ( int num : instructions ) {
int a = tree . query ( 1 , 1 , num - 1 );
int b = tree . query ( 1 , 1 , n ) - tree . query ( 1 , 1 , num );
ans += Math . min ( a , b );
ans %= mod ;
tree . modify ( 1 , num , 1 );
}
return ans ;
}
}
class Node {
int l ;
int r ;
int v ;
}
class SegmentTree {
private Node [] tr ;
public SegmentTree ( int n ) {
tr = new Node [ 4 * n ] ;
for ( int i = 0 ; i < tr . length ; ++ i ) {
tr [ i ] = new Node ();
}
build ( 1 , 1 , n );
}
public void build ( int u , int l , int r ) {
tr [ u ] . l = l ;
tr [ u ] . r = r ;
if ( l == r ) {
return ;
}
int mid = ( l + r ) >> 1 ;
build ( u << 1 , l , mid );
build ( u << 1 | 1 , mid + 1 , r );
}
public void modify ( int u , int x , int v ) {
if ( tr [ u ] . l == x && tr [ u ] . r == x ) {
tr [ u ] . v += v ;
return ;
}
int mid = ( tr [ u ] . l + tr [ u ] . r ) >> 1 ;
if ( x <= mid ) {
modify ( u << 1 , x , v );
} else {
modify ( u << 1 | 1 , x , v );
}
pushup ( u );
}
public void pushup ( int u ) {
tr [ u ] . v = tr [ u << 1 ] . v + tr [ u << 1 | 1 ] . v ;
}
public int query ( int u , int l , int r ) {
if ( tr [ u ] . l >= l && tr [ u ] . r <= r ) {
return tr [ u ] . v ;
}
int mid = ( tr [ u ] . l + tr [ u ] . r ) >> 1 ;
int v = 0 ;
if ( l <= mid ) {
v += query ( u << 1 , l , r );
}
if ( r > mid ) {
v += query ( u << 1 | 1 , l , r );
}
return v ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 class Node {
public :
int l ;
int r ;
int v ;
};
class SegmentTree {
public :
vector < Node *> tr ;
SegmentTree ( int n ) {
tr . resize ( 4 * n );
for ( int i = 0 ; i < tr . size (); ++ i ) tr [ i ] = new Node ();
build ( 1 , 1 , n );
}
void build ( int u , int l , int r ) {
tr [ u ] -> l = l ;
tr [ u ] -> r = r ;
if ( l == r ) return ;
int mid = ( l + r ) >> 1 ;
build ( u << 1 , l , mid );
build ( u << 1 | 1 , mid + 1 , r );
}
void modify ( int u , int x , int v ) {
if ( tr [ u ] -> l == x && tr [ u ] -> r == x ) {
tr [ u ] -> v += v ;
return ;
}
int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ;
if ( x <= mid )
modify ( u << 1 , x , v );
else
modify ( u << 1 | 1 , x , v );
pushup ( u );
}
void pushup ( int u ) {
tr [ u ] -> v = tr [ u << 1 ] -> v + tr [ u << 1 | 1 ] -> v ;
}
int query ( int u , int l , int r ) {
if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) return tr [ u ] -> v ;
int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ;
int v = 0 ;
if ( l <= mid ) v = query ( u << 1 , l , r );
if ( r > mid ) v += query ( u << 1 | 1 , l , r );
return v ;
}
};
class Solution {
public :
int createSortedArray ( vector < int >& instructions ) {
int n = * max_element ( instructions . begin (), instructions . end ());
int mod = 1e9 + 7 ;
SegmentTree * tree = new SegmentTree ( n );
int ans = 0 ;
for ( int num : instructions ) {
int a = tree -> query ( 1 , 1 , num - 1 );
int b = tree -> query ( 1 , 1 , n ) - tree -> query ( 1 , 1 , num );
ans += min ( a , b );
ans %= mod ;
tree -> modify ( 1 , num , 1 );
}
return ans ;
}
};
GitHub