Algorithm for minimizing (s[i]-s[j]+d)/(i-j)

The problem is based on a leetcode contest problem (https://doocs.github.io/leetcode/en/lc/3281/). One can reduce it to following problem: let s be a sorted array and d be an positive integer, minimize (s[i]-s[j]+d)/(i-j). In which i>j.

Most of answer were based on binary search to bound an optimal solution, for which the time complexity is dependent on max(s)-min(s). So is it possible to construct an algorithm that is linear/sub-quadratic w.r.t. size of s?

You can do this in linear time.

First, note that if we were to graph the low points s[i] along with the high points s[i]+d, then our task is the find the line with the smallest possible slope from a low point to a high point on its right.

As we iterate through the high points, we can determine which of the low points on its left connects with the smallest slope, and then remember the best one.

We can find the best connecting point in O(log n) time, because it is guaranteed to be on the upper convex hull of the low points on the left. As we iterate through the high points, we can use the monotone chain algorithm to simultaneously build the upper convex hull of the low points on its left. This takes amortized constant time per point.

Given the upper convex hull of points on the left, we can use a binary search to find the best connecting point, because the slope of the segments of the convex hull decreases monotonically. For all the segments to the left of the best connecting point, the current high point will be underneath or on its line, and for all segments to the right of the best connecting point, the current high point will be above or on its line. This results in an O(n log n) algorithm.

But we don't even need to do a binary search. Since we are only interested in when the minimum slope we've found so far decreases, we never need to consider any points on the upper convex hull to the left of a connection point we've already used. Since the next relevant best connecting point will always be to the right of the current one, we can proceed monotonically through the hull points, permanently deleting segments as the relevant connecting point moves past them.

Here's a linear time implementation in python:

# is n1/d1 < n2/d2 ?
def fracLessThan(n1,d1,n2,d2):
    return n1*d2 < n2*d1

def minSlope(s,d):
    if len(s) < 2:
        return None
    # parallel arrays to keep track of the upper convex hull of previous points
    hullx = [0,1]
    hully = [s[0],s[1]]
    # number of segments removed from left of hull
    hullstart = 0
    # keep track of the best slope as a fraction
    bestSlope = (s[1]+d-s[0], 1)
    for x in range(2, len(s)):
        y = s[x]+d
        # slope from leftmost hull point to (x,y)
        newnum = y - hully[hullstart]
        newden = x - hullx[hullstart]

        # remove segments from the left of the hull util the leftmost point
        # can see (x,y)
        while len(hullx) >= hullstart+2:
            # slope of first hull segment (the one with greatest slope)
            hnum = hully[hullstart+1] - hully[hullstart]
            hden = hullx[hullstart+1] - hullx[hullstart]

            if not fracLessThan(newnum, newden, hnum, hden):
                break

            hullstart += 1
            newnum = y - hully[hullstart]
            newden = x - hullx[hullstart]

        # adjust bestslope if necessary
        if fracLessThan(newnum, newden, bestSlope[0], bestSlope[1]):
            bestSlope = (newnum, newden)
        
        # update the convex hull
        y = s[x]
        while len(hullx) > hullstart+1:
            lastn = hully[-1] - hully[-2]
            lastd = hullx[-1] - hullx[-2]
            testn = y - hully[-2]
            testd = x - hullx[-2]
            if (fracLessThan(testn, testd, lastn, lastd)):
                break
            hullx.pop()
            hully.pop()
        hullx.append(x)
        hully.append(y)

    return bestSlope

ans = minSlope([0,5,6,9,10,12],4)
# prints 11/4
print("min slope is {0}/{1}".format(ans[0], ans[1]))