Java 101 Chapter 8

The next problem is a medium difficulty leetcode excersice called:

1637. 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.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Solution:

1. - So my first though is that we only need to consider the x axis to calculate the maximum width area.
2. We only need to find the largest difference between two given x points of the 2d array given
3. We consider the given points are not ordered, so we do not know where are they located until we iterate through the list.

The first and naive solution is to order the list first, and calculate the differences between the initial element against the following element on the list, if the value is the greatest one, that is our current max width area. Finally return the last max width, which will be the global max.

This solution takes O(n logn) to order the points, considering a quick/merge sort and another O(n) to get the max length.

The following is my passing solution:

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        qSort(points, 0, points.length-1);
        return maxWidthOrdered(points);
    }
    
    public int maxWidthOrdered(int[][] points) {
        int max=points[1][0] - points[0][0];
        int i=1;
while(i< points.length-1){
            if( (points[i+1][0] -points[i][0]) > max ){
                max= (points[i+1][0] -points[i][0]);
}
            i++;
        }
        return max;
    }
    
        static int partition(int arr[][], int low, int high)
    {
        int pivot = arr[high][0];
        int i = (low - 1); // index of smaller element
        for (int j = low; j <= high - 1; j++) {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j][0] <= pivot) {
                i++;
// swap arr[i] and arr[j]
                int[] temp = arr[i];
                arr[i]= arr[j];
                arr[j] = temp;
            }
        }
// swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1][0];
        arr[i + 1][0] = arr[high][0];
        arr[high][0] = temp;
return i + 1;
    }
    static void qSort(int arr[][], int low, int high)
    {
        if (low < high) {
            /* pi is partitioning index, arr[pi] is
            now at right place */
            int pi = partition(arr, low, high);
// Recursively sort elements before
            // partition and after partition
            qSort(arr, low, pi - 1);
            qSort(arr, pi + 1, high);
        }
    }
}