[Leet Code] Widest Vertical Area Between Two Points Containing No Points

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

Problem:

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

Solution:

class Solution(object):
    def maxWidthOfVerticalArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        test = []
        for i in points:
            test.append(i[0])
            
        test.sort(reverse=True)
        
        max_diff = 0
        for i in range(len(test)-1):
            diff = test[i] - test[i+1]
            if diff > max_diff:
                max_diff = diff
        return max_diff

Explanation:

For this, all we really want is the X axis, and we want to arrange them in order so that we can see if there are any points in between two points. To do this, we first go through and get all the x axis they are the first number in each duo [1,0] X = 1, therefore because it’s a list of lists, we can get to each individual list and say that we want the 0th element. We append this onto a list;

Then we want to sort the list in reverse, from highest to lowest. test.sort(reverse=True).

Then we define a max diff variable. Then what we’re going to do is cycle through our list of X values and because they’re in reverse order, we can do i — i+1 and this will give us a positive number. Remember to do len(test)-1 to make sure you don’t get an out of range exception. Then we check if the diff calculated is greater than what’s stored in max_diff, and if so make max_diff = diff, otherwise continue on. Then we return the max_diff.