Scale Engineer

Max Value of Equation

Hard
#1383Time: O(N^2), where N is the number of points. The two nested loops iterate through approximately N^2/2 pairs, leading to a quadratic time complexity.Space: O(1), as we only use a constant amount of extra space for variables.
Patterns
Sliding Window
Data structures
ArrayHeap (Priority Queue)QueueMonotonic Queue

Prompt

You are given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.

Return the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length.

It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.

 

Example 1:

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Output: 4
Explanation: The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

Example 2:

Input: points = [[0,0],[3,0],[9,2]], k = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

 

Constraints:

  • 2 <= points.length <= 105
  • points[i].length == 2
  • -108 <= xi, yi <= 108
  • 0 <= k <= 2 * 108
  • xi < xj for all 1 <= i < j <= points.length
  • xi form a strictly increasing sequence.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves checking every possible pair of points (i, j) where i < j. For each pair, we verify if it satisfies the condition |xi - xj| <= k. If it does, we calculate the equation's value and update our maximum result. This is the most straightforward but least efficient way to solve the problem.

Algorithm

  • Initialize a variable maxVal to the smallest possible integer value.
  • Use a nested loop structure. The outer loop iterates with index j from 1 to n-1, where n is the number of points.
  • The inner loop iterates with index i from 0 to j-1.
  • For each pair of points (i, j), retrieve their coordinates (xi, yi) and (xj, yj).
  • Check if the condition xj - xi <= k is satisfied. Since the points are sorted by x-coordinates, |xi - xj| is equivalent to xj - xi.
  • If the condition holds, calculate the value of the equation: currentVal = yi + yj + xj - xi.
  • Update maxVal by taking the maximum of maxVal and currentVal.
  • After both loops complete, maxVal will hold the maximum value of the equation for any valid pair of points. Return maxVal.

Walkthrough

The problem asks to maximize yi + yj + |xi - xj| given |xi - xj| <= k and i < j. Since the points are sorted by x-coordinates (xi < xj for i < j), the condition |xi - xj| <= k simplifies to xj - xi <= k, and the equation becomes yi + yj + xj - xi. The brute-force algorithm systematically iterates through all pairs of indices (i, j) with i < j. For each pair, it checks if points[j][0] - points[i][0] <= k. If the condition holds, it computes points[i][1] + points[j][1] + points[j][0] - points[i][0] and compares it with the maximum value found so far. This process is repeated for all pairs to find the global maximum.

class Solution {    public int findMaxValueOfEquation(int[][] points, int k) {        int maxVal = Integer.MIN_VALUE;        int n = points.length;        for (int j = 1; j < n; j++) {            for (int i = 0; i < j; i++) {                int xj = points[j][0];                int yj = points[j][1];                int xi = points[i][0];                int yi = points[i][1];                if (xj - xi <= k) {                    maxVal = Math.max(maxVal, yi + yj + xj - xi);                } else {                    // Since points are sorted by x, if the current i is too far,                    // any earlier i will also be too far. We could break here,                    // but the inner loop starts from 0, so this optimization is tricky.                    // A simple loop from j-1 down to 0 would benefit from this break.                }            }        }        return maxVal;    }}

Complexity

Time

O(N^2), where N is the number of points. The two nested loops iterate through approximately N^2/2 pairs, leading to a quadratic time complexity.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

  • It is very simple to understand and implement.

  • It requires no extra space, making it memory efficient.

Cons

  • This approach is very slow due to its O(N^2) time complexity and will result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.

Solutions

class Solution {public  int findMaxValueOfEquation(int[][] points, int k) {    int ans = -(1 << 30);    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->b[0] - a[0]);    for (var p : points) {      int x = p[0], y = p[1];      while (!pq.isEmpty() && x - pq.peek()[1] > k) {        pq.poll();      }      if (!pq.isEmpty()) {        ans = Math.max(ans, x + y + pq.peek()[0]);      }      pq.offer(new int[]{y - x, x});    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem