hard Max Value of Equation

Problem Statement

You are given an array called points containing the coordinates of points on a 2D plane. Each point is represented as points[i] = [x_i, y_i], where x_i and y_i are the x and y coordinates, respectively. The array is sorted by the x-values, meaning x_i < x_j for all 1 <= i < j <= points.length. Additionally, you are given an integer k.

Return the maximum value of the equation y_i + y_j + |x_i - x_j| under the condition that |x_i - x_j| <= k and 1 <= i < j <= points.length.

The problem guarantees that there is at least one valid pair of points that satisfy the condition |x_i - x_j| <= k.

Examples

Example 1:

• Input: points = [[0, 0], [2, 1], [3, 3], [7, 10]], k = 4
• Expected Output: 17
• Justification: By selecting points[2] = [3, 3] and points[3] = [7, 10], we get the equation 3 + 10 + |3 - 7| = 13. The difference in x-values is 4, which is within the allowed range.

Example 2:

• Input: points = [[1, 2], [3, 4], [5, 6]], k = 3
• Expected Output: 12
• Justification: By selecting points[1] = [3, 4] and points[2] = [5, 6], we get the equation 2 + 6 + |3 - 5| = 12. The difference in x-values is 2, which satisfies the condition |x_i - x_j| <= k.

Example 3:

• Input: points = [[2, 4], [5, 1], [8, 7], [10, 3]], k = 5
• Expected Output: 12
• Justification: By selecting points[2] = [8, 7] and points[3] = [10, 3], we get the equation 3 + 7 + |10 - 8| = 12.

Constraints:

• 2 <= points.length <= 10⁵
• points[i].length == 2
• -10⁸ <= x_i, y_i <= 10⁸
• 0 <= k <= 2 * 10⁸
• x_i < x_j for all 1 <= i < j <= points.length
• x_i form a strictly increasing sequence.

Solution

To solve this problem, the goal is to find the maximum value of the equation y_i + y_j + |x_i - x_j| under the condition that |x_i - x_j| <= k for all valid pairs of points i and j.

We can achieve this efficiently by utilizing a monotonic deque (double-ended queue). The deque helps us keep track of potential candidates for the maximum equation value while maintaining a window of points that satisfy the condition |x_i - x_j| <= k. The key insight here is that for a fixed x_j, the optimal y_i + x_i can be derived from the previous points in a way that maximizes the equation. The deque is maintained in a way that the front always contains the best candidate for maximizing the equation. This method allows us to efficiently compute the maximum value without needing to check every possible pair of points.

Step-by-Step Algorithm

1. Initialize a Deque and a Variable for Maximum Value:

   • Create an empty deque deque.
   • Initialize a variable maxValue to store the maximum value of the equation, starting with Integer.MIN_VALUE.

2. Iterate Through Each Point in the Array:

   • For each point [x_i, y_i] in points:

     1. Remove Points That Are Out of the x-Range:

        • While the deque is not empty and the difference x_i - deque.peekFirst()[0] > k, remove points from the front of the deque.
        • Reason: Points that are outside the allowed range (|x_i - x_j| > k) cannot contribute to a valid equation, so they are removed.

     2. Calculate the Potential Maximum Value:

        • If the deque is not empty, calculate the equation value using the point at the front of the deque:
          • currentValue = y_i + x_i + deque.peekFirst()[1] - deque.peekFirst()[0]
        • Update maxValue if currentValue is greater than maxValue.
        • In this step, the point at the front of the deque provides the maximum possible value of y_i + x_i for the current x_j, so it's used to check if it leads to a higher equation value.

     3. Remove Inefficient Points from the Back of the Deque:

        • While the deque is not empty and y_i - x_i >= deque.peekLast()[1] - deque.peekLast()[0], remove points from the back of the deque.
        • Here, points that offer a smaller y_i - x_i are less efficient for future calculations. They are removed to keep the deque optimized.

     4. Add the Current Point to the Deque:

        • Append the current point [x_i, y_i] to the back of the deque. The current point becomes a candidate for maximizing future equation values and is added to the deque.

3. Return the Maximum Value:

   • After processing all points, return maxValue as the result.

Algorithm Walkthrough

Let’s walk through the algorithm with the example: points = [[0, 0], [2, 1], [3, 3], [7, 10]], k = 4.

1. Initialize Deque and maxValue:

   • deque = []
   • maxValue = Integer.MIN_VALUE

2. Process each point:

   • Point [0, 0]:

     • Deque is empty, so no points are removed.
     • No calculation for maxValue since deque is empty.
     • Add [0, 0] to the deque.
     • deque = [[0, 0]]

   • Point [2, 1]:

     • Check if any points in the deque are out of range (x_i - deque.peekFirst()[0] > 4):
       • No points are out of range, so no removal.
     • Calculate the potential maxValue using the front of the deque:
       • currentValue = 1 + 2 + (0 - 0) = 3
       • Update maxValue to 3.
     • Remove inefficient points from the back of the deque:
       • 1 - 2 is not greater than 0 - 0, so no points are removed.
     • Add [2, 1] to the deque.
     • deque = [[0, 0], [2, 1]]

   • Point [3, 3]:

     • Check if any points in the deque are out of range (x_i - deque.peekFirst()[0] > 4):
       • No points are out of range, so no removal.
     • Calculate the potential maxValue using the front of the deque:
       • currentValue = 3 + 3 + (0 - 0) = 6
       • Update maxValue to 6.
     • Remove inefficient points from the back of the deque:
       • 3 - 3 is greater than or equal to 1 - 2, so remove [2, 1].
       • 3 - 3 is greater than or equal to 0 - 0, so remove [0, 0].
     • Add [3, 3] to the deque.
     • deque = [[3, 3]]

   • Point [7, 10]:

     • Check if any points in the deque are out of range (x_i - deque.peekFirst()[0] > 4):
       • [3, 3] is not out of range as 7 - 3 = 4 is less than or equal to 4
     • Calculate the potential maxValue using the front of the deque:
       • currentValue = 10 + 7 + (3 - 3) = 17
       • Update maxValue to 17.
     • Remove inefficient points from the back of the deque:
       • 10 - 7 is greater than 3 - 3. So, remove [3, 3].
     • Add [7, 10] to the deque.
     • deque = [[7, 10]]

3. Final maxValue:

   • After processing all points, the final maxValue is 17.

Code

import java.util.*;

class Solution {

  public int findMaxValueOfEquation(int[][] points, int k) {
    Deque<int[]> deque = new LinkedList<>();
    int maxValue = Integer.MIN_VALUE;

    for (int[] point : points) {
      int x = point[0];
      int y = point[1];

      // Remove points that are out of the x range (xi - xj > k)
      while (!deque.isEmpty() && x - deque.peekFirst()[0] > k) {
        deque.pollFirst();
      }

      // Calculate the equation value with the front of the deque
      if (!deque.isEmpty()) {
        maxValue = Math.max(
          maxValue,
          y + x + deque.peekFirst()[1] - deque.peekFirst()[0]
        );
      }

      // Remove points from the back of the deque that are less efficient
      while (
        !deque.isEmpty() && y - x >= deque.peekLast()[1] - deque.peekLast()[0]
      ) {
        deque.pollLast();
      }

      // Add the current point to the deque
      deque.offerLast(new int[] { x, y });
    }

    return maxValue;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[][] points1 = { { 0, 0 }, { 2, 1 }, { 3, 3 }, { 7, 10 } };
    int k1 = 4;
    System.out.println(
      "Example 1: " + solution.findMaxValueOfEquation(points1, k1)
    ); // Expected output: 17

    // Example 2
    int[][] points2 = { { 1, 2 }, { 3, 4 }, { 5, 6 } };
    int k2 = 3;
    System.out.println(
      "Example 2: " + solution.findMaxValueOfEquation(points2, k2)
    ); // Expected output: 12

    // Example 3
    int[][] points3 = { { 2, 4 }, { 5, 1 }, { 8, 7 }, { 10, 3 } };
    int k3 = 5;
    System.out.println(
      "Example 3: " + solution.findMaxValueOfEquation(points3, k3)
    ); // Expected output: 12
  }
}

Complexity Analysis

Time Complexity

The algorithm iterates through the list of points exactly once, processing each point in constant time concerning the operations on the deque. Each point is added and removed from the deque at most once, leading to a time complexity of , where n is the number of points.

Space Complexity

The space complexity is as well, due to the storage of points in the deque. In the worst case, all points could be stored in the deque simultaneously.