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>> maxQ;  // (y - x, x) max queue

    for (const vector<int>& point : points) {
      const int x = point[0];
      const int y = point[1];
      // Remove the invalid points, xj - xi > k.
      while (!maxQ.empty() && x - maxQ.front().second > k)
        maxQ.pop_front();
      if (!maxQ.empty())
        ans = max(ans, x + y + maxQ.front().first);
      // Remove the points that contribute less value and have a bigger x.
      while (!maxQ.empty() && y - x >= maxQ.back().first)
        maxQ.pop_back();
      maxQ.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>> maxQ = new ArrayDeque<>(); // (y - x, x)

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

    return ans;
  }
}

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

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

    return ans