Problem statement

https://leetcode.com/problems/max-value-of-equation/

Solution

There are different solutions, and the fastest one uses the idea of monotonic deque. What is actually asked in this problem is find max(yi - xi + (yj + xj)), where j > i and xj - xi <= k. The idea is to keep sliding window of points, such that:

  1. while deq and deq[0][0] < x - k: deq.popleft() In this line we make sure, that we do not have old points, that is if |x_j - x_i| > k, we remove this point from left side of or sliding window.
  2. if deq: ans = max(ans, deq[0][1] + x + y). In this line we update our answer: in fact we need to find (yi - xi + (yj + xj)) and if right end of our window j is fixed, we need to choose maximum among yi - xi in our window.
  3. while deq and y - x >= deq[-1][1]: deq.pop(): we have always decreasing elements in our deque, by key (y - x), so the biggest element will be the first one, we used it in step 2.
  4. Finally we append key (x, y - x) to our deque to the right.

Note, that we can as well just append index i to deque, and then code will be more difficult to read.

Complexity

Time complexity is O(n), space is O(n) as well.

Code

class Solution:
    def findMaxValueOfEquation(self, P, k):
        deq, ans = deque(), -float("inf")
        
        for x, y in P:
            while deq and deq[0][0] < x - k: deq.popleft()  
            if deq: ans = max(ans, deq[0][1] + x + y)
            while deq and y - x >= deq[-1][1]: deq.pop()
            deq.append((x, y-x))
          
        return ans

Remark

Other ways to solve is heap with lazy updates with complexity O(n log n) or sorted list with O(n log n) complexity as well.