Leetcode: 1499. Max Value of Equation

Can we derive an invariant based on the smallest possible examples? Be \(i\) and \(j\) two points where \(x_j \leq x_i\), \(j < i\), \(x_i - x_j \leq k\). The formula becomes \(y_j + y_i + x_i - x_j = (y_j - x_j) + (y_i + x_i)\). To maximize the formula, we have to pick the point \(j\) that maximizes \(y_j - x_j\) and this can be done by keeping a list of candidates sorted by this value. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from typing import List
from heapq import heappush, heappop


class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        pq = []
        ans = float("-inf")
        for p in points:
            while pq and p[0] - pq[0][1][0] > k:
                heappop(pq)

            if pq:
                cur = p[1] + pq[0][1][1] + (p[0] - pq[0][1][0])
                if cur > ans:
                    ans = cur
            heappush(pq, (p[0] - p[1], p))
        return ans


assert Solution().findMaxValueOfEquation([[1, 3], [2, 0], [5, 10], [6, -10]], 1) == 4
assert Solution().findMaxValueOfEquation([[0, 0], [3, 0], [9, 2]], 3) == 3