1499. Max Value of Equation

Approach 1: Heap

• Time: $O(n\log n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    int ans = INT_MIN;
    priority_queue<pair<int, int>> maxHeap;  // (y - x, x)

    for (const vector<int>& p : points) {
      const int x = p[0];
      const int y = p[1];
      while (!maxHeap.empty() && x - maxHeap.top().second > k)
        maxHeap.pop();
      if (!maxHeap.empty())
        ans = max(ans, x + y + maxHeap.top().first);
      maxHeap.emplace(y - x, x);
    }

    return ans;
  }
};

class Solution {
  public int findMaxValueOfEquation(int[][] points, int k) {
    int ans = Integer.MIN_VALUE;
    // (y - x, x)
    Queue<Pair<Integer, Integer>> maxHeap =
        new PriorityQueue<>((a, b)
                                -> a.getKey().equals(b.getKey()) ? b.getValue() - a.getValue()
                                                                 : b.getKey() - a.getKey());

    for (int[] p : points) {
      final int x = p[0];
      final int y = p[1];
      while (!maxHeap.isEmpty() && x - maxHeap.peek().getValue() > k)
        maxHeap.poll();
      if (!maxHeap.isEmpty())
        ans = Math.max(ans, x + y + maxHeap.peek().getKey());
      maxHeap.offer(new Pair<>(y - x, x));
    }

    return ans;
  }
}

class Solution:
  def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    ans = -math.inf
    maxHeap = []  # (y - x, x)

    for x, y in points:
      while maxHeap and x + maxHeap[0][1] > k:
        heapq.heappop(maxHeap)
      if maxHeap:
        ans = max(ans, x + y - maxHeap[0][0])
      heapq.heappush(maxHeap, (x - y, -x))

    return ans

Approach 2: Monotonic Queue

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
    int ans = INT_MIN;
    deque<pair<int, int>> dq;  // (y - x, x) max queue

    for (const vector<int>& p : points) {
      const int x = p[0];
      const int y = p[1];
      // Remove invalid points, xj - xi > k
      while (!dq.empty() && x - dq.front().second > k)
        dq.pop_front();
      if (!dq.empty())
        ans = max(ans, x + y + dq.front().first);
      // Remove points that contribute less value and have bigger x
      while (!dq.empty() && y - x >= dq.back().first)
        dq.pop_back();
      dq.emplace_back(y - x, x);
    }

    return ans;
  }
};

class Solution {
  public int findMaxValueOfEquation(int[][] points, int k) {
    int ans = Integer.MIN_VALUE;
    Deque<Pair<Integer, Integer>> dq = new ArrayDeque<>(); // (y - x, x) max queue

    for (int[] p : points) {
      final int x = p[0];
      final int y = p[1];
      // Remove invalid points, xj - xi > k
      while (!dq.isEmpty() && x - dq.peekFirst().getValue() > k)
        dq.pollFirst();
      if (!dq.isEmpty())
        ans = Math.max(ans, x + y + dq.peekFirst().getKey());
      // Remove points that contribute less value and have bigger x
      while (!dq.isEmpty() && y - x >= dq.peekLast().getKey())
        dq.pollLast();
      dq.offerLast(new Pair<>(y - x, x));
    }

    return ans;
  }
}

class Solution:
  def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
    ans = -math.inf
    dq = collections.deque()  # (y - x, x) max queue

    for x, y in points:
      # Remove invalid points, xj - xi > k
      while dq and x - dq[0][1] > k:
        dq.popleft()
      if dq:
        ans = max(ans, x + y + dq[0][0])
      # Remove points that contribute less value and have bigger x
      while dq and y - x >= dq[-1][0]:
        dq.pop()
      dq.append((y - x, x))

    return ans