![https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/]

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.

ex1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
 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 Solution {
    private static final Random RANDOM = new Random();
    public int maxWidthOfVerticalArea(int[][] points) {
        // shuffle(points);
        sort(points);

        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            max = Math.max(max, points[i + 1][0] - points[i][0]);
        }
        return max;
    }
    
    void sort(int[][] points) {

        sort(points, 0, points.length - 1);
    }
    
    int partition(int[][] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        
        while (true) {
            while (less(a[++i], a[lo])) {
                if (i == hi) break;
            }   
            while (less(a[lo], a[--j])) {
                if (j == lo) break;
            }
            if (i >= j) break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }
                   
    boolean less(int[] a, int[] b) {
        return (a[0] - b[0]) < 0;
    }
    
    void swap(int[][] a, int i, int j) {
        int x = a[i][0];
        int y = a[i][1];
        
        a[i][0] = a[j][0];
        a[i][1] = a[j][1];
        
        a[j][0] = x;
        a[j][1] = y;
    }
    
    void sort(int[][] points, int lo, int hi) {
        if (lo >= hi) return;
        int j = partition(points, lo, hi);

        sort(points, lo, j - 1);
        sort(points, j + 1, hi);
    }

    void shuffle(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            swap(a, i, RANDOM.nextInt(a.length));
        }
    }
}