CareerCup

We should start by remembering that slope between two points is:

slope = (y2 - y1)/(x2 - x1)
or
slope = (change in y)/(change in x)

Effectively this problem asks us to locate two pairs of values who have a maximum difference between their y coordinates and a minimum diff between their x coordinates.

The brute force method is to compare each pairing to every other pairing but that is clearly not what is being asked for as it would take O(n^2) time.

While I forget the name of the concept (or if it has a common name), you can assume that given a set of points on any 2d plane with x and y axis, when sorted by x axis, the highest slope will always be between two points adjacent on the x axis.

To see this better, try drawing 3 points on a plane, look at how steep the line between each of them is, notice the line between non-adjacent points is never the steepest. At best, all three slopes are the same if you have them all aligned. If you try all combinations with four points, you will see the same principle still holds. And with 5 pts, etc etc. It can be summarized, non-algebraically, as

Given points a,b,c on a 2D plane where b has the median x-axis value, creating a triangle with these three points requires that either b->a or b->c will always be steeper than a->c, based on whether b is located above or below the a->c line.

If b is below the line, b->c will always be greater than a->c, if it is above the line, a->b will always be greater. This is the positive direction of slope to reach a common point from a closer x-axis position, so it will always be steeper. If b is on the a->c line, its slope is the same as a->c.

If we use this postulate within our solution, we can say that once we have sorted the points by x-coordinate, the highest slope will be found at one of the adjacent pairs of points.

In python, the solution would look like:

def find_highest_slope(points):
    output = ((1,1),(1,1))
    max_slope = 0
    #use some method to sort points by x axis
    for x in range(1,len(points)):
        delta_y = points[x][1] - points[x-1][1]
        delta_x = points[x][0]-points[x-1][0]
        if delta_x == 0:
            continue
        slope = (delta_y)/(delta_x)
        if slope > max_slope:
            max_slope = slope
            output = ((points[x-1][0],points[x-1][1]),(points[x][0],points[x][1]))

    return output

The part shown here will take O(n) time, as it merely compares each coordinate to its previous neighbor. The sorting may take longer, but assuming you use a heapsort or similar, you can say that the solution takes O(n log n) which beats the O(n^2) done with the brute force solution.

Javeed, well explained, Thanks.