Binary Indexed Tree
Segment Tree
Array
Binary Search
Divide and Conquer
Ordered Set
Merge Sort
Description
You are given two 0-indexed arrays nums1
and nums2
of length n
, both of which are permutations of [0, 1, ..., n - 1]
.
A good triplet is a set of 3
distinct values which are present in increasing order by position both in nums1
and nums2
. In other words, if we consider pos1v
as the index of the value v
in nums1
and pos2v
as the index of the value v
in nums2
, then a good triplet will be a set (x, y, z)
where 0 <= x, y, z <= n - 1
, such that pos1x < pos1y < pos1z
and pos2x < pos2y < pos2z
.
Return the total number of good triplets .
Example 1:
Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation:
There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z . They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3).
Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z . Hence, there is only 1 good triplet.
Example 2:
Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).
Constraints:
n == nums1.length == nums2.length
3 <= n <= 105
0 <= nums1[i], nums2[i] <= n - 1
nums1
and nums2
are permutations of [0, 1, ..., n - 1]
.
Solutions
Solution 1
Python3 Java C++ Go
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 class BinaryIndexedTree :
def __init__ ( self , n ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
@staticmethod
def lowbit ( x ):
return x & - x
def update ( self , x , delta ):
while x <= self . n :
self . c [ x ] += delta
x += BinaryIndexedTree . lowbit ( x )
def query ( self , x ):
s = 0
while x > 0 :
s += self . c [ x ]
x -= BinaryIndexedTree . lowbit ( x )
return s
class Solution :
def goodTriplets ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int :
pos = { v : i for i , v in enumerate ( nums2 , 1 )}
ans = 0
n = len ( nums1 )
tree = BinaryIndexedTree ( n )
for num in nums1 :
p = pos [ num ]
left = tree . query ( p )
right = n - p - ( tree . query ( n ) - tree . query ( p ))
ans += left * right
tree . update ( p , 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
44
45
46
47
48
49 class Solution {
public long goodTriplets ( int [] nums1 , int [] nums2 ) {
int n = nums1 . length ;
int [] pos = new int [ n ] ;
BinaryIndexedTree tree = new BinaryIndexedTree ( n );
for ( int i = 0 ; i < n ; ++ i ) {
pos [ nums2 [ i ]] = i + 1 ;
}
long ans = 0 ;
for ( int num : nums1 ) {
int p = pos [ num ] ;
long left = tree . query ( p );
long right = n - p - ( tree . query ( n ) - tree . query ( p ));
ans += left * right ;
tree . update ( p , 1 );
}
return ans ;
}
}
class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
c = new int [ n + 1 ] ;
}
public void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
public int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ] ;
x -= lowbit ( x );
}
return s ;
}
public static int lowbit ( int x ) {
return x & - x ;
}
}
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 class BinaryIndexedTree {
public :
int n ;
vector < int > c ;
BinaryIndexedTree ( int _n )
: n ( _n )
, c ( _n + 1 ) {}
void update ( int x , int delta ) {
while ( x <= n ) {
c [ x ] += delta ;
x += lowbit ( x );
}
}
int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ];
x -= lowbit ( x );
}
return s ;
}
int lowbit ( int x ) {
return x & - x ;
}
};
class Solution {
public :
long long goodTriplets ( vector < int >& nums1 , vector < int >& nums2 ) {
int n = nums1 . size ();
vector < int > pos ( n );
for ( int i = 0 ; i < n ; ++ i ) pos [ nums2 [ i ]] = i + 1 ;
BinaryIndexedTree * tree = new BinaryIndexedTree ( n );
long long ans = 0 ;
for ( int & num : nums1 ) {
int p = pos [ num ];
int left = tree -> query ( p );
int right = n - p - ( tree -> query ( n ) - tree -> query ( p ));
ans += 1l l * left * right ;
tree -> update ( p , 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
44
45
46
47 type BinaryIndexedTree struct {
n int
c [] int
}
func newBinaryIndexedTree ( n int ) * BinaryIndexedTree {
c := make ([] int , n + 1 )
return & BinaryIndexedTree { n , c }
}
func ( this * BinaryIndexedTree ) lowbit ( x int ) int {
return x & - x
}
func ( this * BinaryIndexedTree ) update ( x , delta int ) {
for x <= this . n {
this . c [ x ] += delta
x += this . lowbit ( x )
}
}
func ( this * BinaryIndexedTree ) query ( x int ) int {
s := 0
for x > 0 {
s += this . c [ x ]
x -= this . lowbit ( x )
}
return s
}
func goodTriplets ( nums1 [] int , nums2 [] int ) int64 {
n := len ( nums1 )
pos := make ([] int , n )
for i , v := range nums2 {
pos [ v ] = i + 1
}
tree := newBinaryIndexedTree ( n )
var ans int64
for _ , num := range nums1 {
p := pos [ num ]
left := tree . query ( p )
right := n - p - ( tree . query ( n ) - tree . query ( p ))
ans += int64 ( left ) * int64 ( right )
tree . update ( p , 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
59
60 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 goodTriplets ( self , nums1 : List [ int ], nums2 : List [ int ]) -> int :
pos = { v : i for i , v in enumerate ( nums2 , 1 )}
ans = 0
n = len ( nums1 )
tree = SegmentTree ( n )
for num in nums1 :
p = pos [ num ]
left = tree . query ( 1 , 1 , p )
right = n - p - ( tree . query ( 1 , 1 , n ) - tree . query ( 1 , 1 , p ))
ans += left * right
tree . modify ( 1 , p , 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
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
79
80
81 class Solution {
public long goodTriplets ( int [] nums1 , int [] nums2 ) {
int n = nums1 . length ;
int [] pos = new int [ n ] ;
SegmentTree tree = new SegmentTree ( n );
for ( int i = 0 ; i < n ; ++ i ) {
pos [ nums2 [ i ]] = i + 1 ;
}
long ans = 0 ;
for ( int num : nums1 ) {
int p = pos [ num ] ;
long left = tree . query ( 1 , 1 , p );
long right = n - p - ( tree . query ( 1 , 1 , n ) - tree . query ( 1 , 1 , p ));
ans += left * right ;
tree . modify ( 1 , p , 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
71 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 :
long long goodTriplets ( vector < int >& nums1 , vector < int >& nums2 ) {
int n = nums1 . size ();
vector < int > pos ( n );
for ( int i = 0 ; i < n ; ++ i ) pos [ nums2 [ i ]] = i + 1 ;
SegmentTree * tree = new SegmentTree ( n );
long long ans = 0 ;
for ( int & num : nums1 ) {
int p = pos [ num ];
int left = tree -> query ( 1 , 1 , p );
int right = n - p - ( tree -> query ( 1 , 1 , n ) - tree -> query ( 1 , 1 , p ));
ans += 1l l * left * right ;
tree -> modify ( 1 , p , 1 );
}
return ans ;
}
};
GitHub