Array
Sorting
Description
Given n
points
on a 2D plane where points[i] = [xi , yi ]
, Return the widest vertical area between two points such that no points are inside the area.
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Example 1:
Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.
Example 2:
Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3
Constraints:
n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi , yi <= 109
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
class Solution :
def maxWidthOfVerticalArea ( self , points : List [ List [ int ]]) -> int :
points . sort ()
return max ( b [ 0 ] - a [ 0 ] for a , b in pairwise ( points ))
class Solution {
public int maxWidthOfVerticalArea ( int [][] points ) {
Arrays . sort ( points , ( a , b ) -> a [ 0 ] - b [ 0 ] );
int ans = 0 ;
for ( int i = 0 ; i < points . length - 1 ; ++ i ) {
ans = Math . max ( ans , points [ i + 1 ][ 0 ] - points [ i ][ 0 ] );
}
return ans ;
}
}
class Solution {
public :
int maxWidthOfVerticalArea ( vector < vector < int >>& points ) {
sort ( points . begin (), points . end ());
int ans = 0 ;
for ( int i = 0 ; i < points . size () - 1 ; ++ i ) {
ans = max ( ans , points [ i + 1 ][ 0 ] - points [ i ][ 0 ]);
}
return ans ;
}
};
func maxWidthOfVerticalArea ( points [][] int ) ( ans int ) {
sort . Slice ( points , func ( i , j int ) bool { return points [ i ][ 0 ] < points [ j ][ 0 ] })
for i , p := range points [ 1 :] {
ans = max ( ans , p [ 0 ] - points [ i ][ 0 ])
}
return
}
function maxWidthOfVerticalArea ( points : number [][]) : number {
points . sort (( a , b ) => a [ 0 ] - b [ 0 ]);
let ans = 0 ;
for ( let i = 1 ; i < points . length ; ++ i ) {
ans = Math . max ( ans , points [ i ][ 0 ] - points [ i - 1 ][ 0 ]);
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 /**
* @param {number[][]} points
* @return {number}
*/
var maxWidthOfVerticalArea = function ( points ) {
points . sort (( a , b ) => a [ 0 ] - b [ 0 ]);
let ans = 0 ;
let px = points [ 0 ][ 0 ];
for ( const [ x , _ ] of points ) {
ans = Math . max ( ans , x - px );
px = x ;
}
return ans ;
};
Solution 2
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def maxWidthOfVerticalArea ( self , points : List [ List [ int ]]) -> int :
nums = [ x for x , _ in points ]
n = len ( nums )
mi , mx = min ( nums ), max ( nums )
bucket_size = max ( 1 , ( mx - mi ) // ( n - 1 ))
bucket_count = ( mx - mi ) // bucket_size + 1
buckets = [[ inf , - inf ] for _ in range ( bucket_count )]
for x in nums :
i = ( x - mi ) // bucket_size
buckets [ i ][ 0 ] = min ( buckets [ i ][ 0 ], x )
buckets [ i ][ 1 ] = max ( buckets [ i ][ 1 ], x )
ans = 0
prev = inf
for curmin , curmax in buckets :
if curmin > curmax :
continue
ans = max ( ans , curmin - prev )
prev = curmax
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 class Solution {
public int maxWidthOfVerticalArea ( int [][] points ) {
int n = points . length ;
int [] nums = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
nums [ i ] = points [ i ][ 0 ] ;
}
final int inf = 1 << 30 ;
int mi = inf , mx = - inf ;
for ( int v : nums ) {
mi = Math . min ( mi , v );
mx = Math . max ( mx , v );
}
int bucketSize = Math . max ( 1 , ( mx - mi ) / ( n - 1 ));
int bucketCount = ( mx - mi ) / bucketSize + 1 ;
int [][] buckets = new int [ bucketCount ][ 2 ] ;
for ( var bucket : buckets ) {
bucket [ 0 ] = inf ;
bucket [ 1 ] = - inf ;
}
for ( int v : nums ) {
int i = ( v - mi ) / bucketSize ;
buckets [ i ][ 0 ] = Math . min ( buckets [ i ][ 0 ] , v );
buckets [ i ][ 1 ] = Math . max ( buckets [ i ][ 1 ] , v );
}
int prev = inf ;
int ans = 0 ;
for ( var bucket : buckets ) {
if ( bucket [ 0 ] > bucket [ 1 ] ) {
continue ;
}
ans = Math . max ( ans , bucket [ 0 ] - prev );
prev = bucket [ 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 class Solution {
public :
int maxWidthOfVerticalArea ( vector < vector < int >>& points ) {
int n = points . size ();
vector < int > nums ;
for ( auto & p : points ) {
nums . push_back ( p [ 0 ]);
}
const int inf = 1 << 30 ;
int mi = inf , mx = - inf ;
for ( int v : nums ) {
mi = min ( mi , v );
mx = max ( mx , v );
}
int bucketSize = max ( 1 , ( mx - mi ) / ( n - 1 ));
int bucketCount = ( mx - mi ) / bucketSize + 1 ;
vector < pair < int , int >> buckets ( bucketCount , { inf , - inf });
for ( int v : nums ) {
int i = ( v - mi ) / bucketSize ;
buckets [ i ]. first = min ( buckets [ i ]. first , v );
buckets [ i ]. second = max ( buckets [ i ]. second , v );
}
int ans = 0 ;
int prev = inf ;
for ( auto [ curmin , curmax ] : buckets ) {
if ( curmin > curmax ) continue ;
ans = max ( ans , curmin - prev );
prev = curmax ;
}
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 func maxWidthOfVerticalArea ( points [][] int ) ( ans int ) {
n := len ( points )
nums := make ([] int , 0 , n )
for _ , p := range points {
nums = append ( nums , p [ 0 ])
}
const inf = 1 << 30
mi , mx := inf , - inf
for _ , v := range nums {
mi = min ( mi , v )
mx = max ( mx , v )
}
bucketSize := max ( 1 , ( mx - mi ) / ( n - 1 ))
bucketCount := ( mx - mi ) / bucketSize + 1
buckets := make ([][] int , bucketCount )
for i := range buckets {
buckets [ i ] = [] int { inf , - inf }
}
for _ , v := range nums {
i := ( v - mi ) / bucketSize
buckets [ i ][ 0 ] = min ( buckets [ i ][ 0 ], v )
buckets [ i ][ 1 ] = max ( buckets [ i ][ 1 ], v )
}
prev := inf
for _ , bucket := range buckets {
if bucket [ 0 ] > bucket [ 1 ] {
continue
}
ans = max ( ans , bucket [ 0 ] - prev )
prev = bucket [ 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 function maxWidthOfVerticalArea ( points : number [][]) : number {
const nums : number [] = points . map ( point => point [ 0 ]);
const inf = 1 << 30 ;
const n = nums . length ;
let mi = inf ;
let mx = - inf ;
for ( const x of nums ) {
mi = Math . min ( mi , x );
mx = Math . max ( mx , x );
}
const bucketSize = Math . max ( 1 , Math . floor (( mx - mi ) / ( n - 1 )));
const bucketCount = Math . floor (( mx - mi ) / bucketSize ) + 1 ;
const buckets = new Array ( bucketCount ). fill ( 0 ). map (() => [ inf , - inf ]);
for ( const x of nums ) {
const i = Math . floor (( x - mi ) / bucketSize );
buckets [ i ][ 0 ] = Math . min ( buckets [ i ][ 0 ], x );
buckets [ i ][ 1 ] = Math . max ( buckets [ i ][ 1 ], x );
}
let prev = inf ;
let ans = 0 ;
for ( const [ left , right ] of buckets ) {
if ( left > right ) {
continue ;
}
ans = Math . max ( ans , left - prev );
prev = right ;
}
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 /**
* @param {number[][]} points
* @return {number}
*/
var maxWidthOfVerticalArea = function ( points ) {
const nums = points . map ( point => point [ 0 ]);
const inf = 1 << 30 ;
const n = nums . length ;
let mi = inf ;
let mx = - inf ;
for ( const x of nums ) {
mi = Math . min ( mi , x );
mx = Math . max ( mx , x );
}
const bucketSize = Math . max ( 1 , Math . floor (( mx - mi ) / ( n - 1 )));
const bucketCount = Math . floor (( mx - mi ) / bucketSize ) + 1 ;
const buckets = new Array ( bucketCount ). fill ( 0 ). map (() => [ inf , - inf ]);
for ( const x of nums ) {
const i = Math . floor (( x - mi ) / bucketSize );
buckets [ i ][ 0 ] = Math . min ( buckets [ i ][ 0 ], x );
buckets [ i ][ 1 ] = Math . max ( buckets [ i ][ 1 ], x );
}
let prev = inf ;
let ans = 0 ;
for ( const [ left , right ] of buckets ) {
if ( left > right ) {
continue ;
}
ans = Math . max ( ans , left - prev );
prev = right ;
}
return ans ;
};
GitHub