Stack
Array
Binary Search
Ordered Set
Monotonic Stack
Description
Given an array of n
integers nums
, a 132 pattern is a subsequence of three integers nums[i]
, nums[j]
and nums[k]
such that i < j < k
and nums[i] < nums[k] < nums[j]
.
Return true
if there is a 132 pattern in nums
, otherwise, return false
.
Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109
Solutions
Solution 1
Solution 2
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
30
31
32
33 class BinaryIndexedTree :
def __init__ ( self , n ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
def update ( self , x , delta ):
while x <= self . n :
self . c [ x ] += delta
x += x & - x
def query ( self , x ):
s = 0
while x :
s += self . c [ x ]
x -= x & - x
return s
class Solution :
def find132pattern ( self , nums : List [ int ]) -> bool :
s = sorted ( set ( nums ))
n = len ( nums )
left = [ inf ] * ( n + 1 )
for i , x in enumerate ( nums ):
left [ i + 1 ] = min ( left [ i ], x )
tree = BinaryIndexedTree ( len ( s ))
for i in range ( n - 1 , - 1 , - 1 ):
x = bisect_left ( s , nums [ i ]) + 1
y = bisect_left ( s , left [ i ]) + 1
if x > y and tree . query ( x - 1 ) > tree . query ( y ):
return True
tree . update ( x , 1 )
return False
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 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 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 boolean find132pattern ( int [] nums ) {
int [] s = nums . clone ();
Arrays . sort ( s );
int n = nums . length ;
int m = 0 ;
int [] left = new int [ n + 1 ] ;
left [ 0 ] = 1 << 30 ;
for ( int i = 0 ; i < n ; ++ i ) {
left [ i + 1 ] = Math . min ( left [ i ] , nums [ i ] );
if ( i == 0 || s [ i ] != s [ i - 1 ] ) {
s [ m ++] = s [ i ] ;
}
}
BinaryIndexedTree tree = new BinaryIndexedTree ( m );
for ( int i = n - 1 ; i >= 0 ; -- i ) {
int x = search ( s , m , nums [ i ] );
int y = search ( s , m , left [ i ] );
if ( x > y && tree . query ( x - 1 ) > tree . query ( y )) {
return true ;
}
tree . update ( x , 1 );
}
return false ;
}
private int search ( int [] nums , int r , int x ) {
int l = 0 ;
while ( l < r ) {
int mid = ( l + r ) >> 1 ;
if ( nums [ mid ] >= x ) {
r = mid ;
} else {
l = mid + 1 ;
}
}
return l + 1 ;
}
}
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 class BinaryIndexedTree {
public :
BinaryIndexedTree ( int n ) {
this -> n = n ;
this -> c = vector < int > ( n + 1 , 0 );
}
void update ( int x , int val ) {
while ( x <= n ) {
c [ x ] += val ;
x += x & - x ;
}
}
int query ( int x ) {
int s = 0 ;
while ( x > 0 ) {
s += c [ x ];
x -= x & - x ;
}
return s ;
}
private :
int n ;
vector < int > c ;
};
class Solution {
public :
bool find132pattern ( vector < int >& nums ) {
vector < int > s = nums ;
sort ( s . begin (), s . end ());
s . erase ( unique ( s . begin (), s . end ()), s . end ());
BinaryIndexedTree tree ( s . size ());
int n = nums . size ();
int left [ n + 1 ];
memset ( left , 63 , sizeof ( left ));
for ( int i = 0 ; i < n ; ++ i ) {
left [ i + 1 ] = min ( left [ i ], nums [ i ]);
}
for ( int i = nums . size () - 1 ; ~ i ; -- i ) {
int x = lower_bound ( s . begin (), s . end (), nums [ i ]) - s . begin () + 1 ;
int y = lower_bound ( s . begin (), s . end (), left [ i ]) - s . begin () + 1 ;
if ( x > y && tree . query ( x - 1 ) > tree . query ( y )) {
return true ;
}
tree . update ( x , 1 );
}
return false ;
}
};
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 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 , val int ) {
for x <= this . n {
this . c [ x ] += val
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 find132pattern ( nums [] int ) bool {
n := len ( nums )
s := make ([] int , n )
left := make ([] int , n + 1 )
left [ 0 ] = 1 << 30
copy ( s , nums )
sort . Ints ( s )
m := 0
for i := 0 ; i < n ; i ++ {
left [ i + 1 ] = min ( left [ i ], nums [ i ])
if i == 0 || s [ i ] != s [ i - 1 ] {
s [ m ] = s [ i ]
m ++
}
}
s = s [: m ]
tree := newBinaryIndexedTree ( m )
for i := n - 1 ; i >= 0 ; i -- {
x := sort . SearchInts ( s , nums [ i ]) + 1
y := sort . SearchInts ( s , left [ i ]) + 1
if x > y && tree . query ( x - 1 ) > tree . query ( y ) {
return true
}
tree . update ( x , 1 )
}
return false
}
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 class BinaryIndextedTree {
n : number ;
c : number [];
constructor ( n : number ) {
this . n = n ;
this . c = new Array ( n + 1 ). fill ( 0 );
}
update ( x : number , val : number ) : void {
while ( x <= this . n ) {
this . c [ x ] += val ;
x += x & - x ;
}
}
query ( x : number ) : number {
let s = 0 ;
while ( x ) {
s += this . c [ x ];
x -= x & - x ;
}
return s ;
}
}
function find132pattern ( nums : number []) : boolean {
let s : number [] = [... nums ];
s . sort (( a , b ) => a - b );
const n = nums . length ;
const left : number [] = new Array ( n + 1 ). fill ( 1 << 30 );
let m = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
left [ i + 1 ] = Math . min ( left [ i ], nums [ i ]);
if ( i == 0 || s [ i ] != s [ i - 1 ]) {
s [ m ++ ] = s [ i ];
}
}
s = s . slice ( 0 , m );
const tree = new BinaryIndextedTree ( m );
for ( let i = n - 1 ; i >= 0 ; -- i ) {
const x = search ( s , nums [ i ]);
const y = search ( s , left [ i ]);
if ( x > y && tree . query ( x - 1 ) > tree . query ( y )) {
return true ;
}
tree . update ( x , 1 );
}
return false ;
}
function search ( nums : number [], x : number ) : number {
let l = 0 ,
r = nums . length - 1 ;
while ( l < r ) {
const mid = ( l + r ) >> 1 ;
if ( nums [ mid ] >= x ) {
r = mid ;
} else {
l = mid + 1 ;
}
}
return l + 1 ;
}
GitHub