We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Value of Equation

Number: 1622

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a sorted list of points on the 2D-plane where each point is represented as [x, y] with strictly increasing x-values, and an integer k, find the maximum value of the equation:
  y_i + y_j + |x_i - x_j|
subject to the constraint |x_i - x_j| <= k for any pair of points with i < j.

Key Insights

  • The equation can be rewritten as (y_i + x_i) + (y_j - x_j) since x_i < x_j.
  • For every current point j, we are looking to pair it with a previous point i that maximizes (y_i + x_i), provided that x_j - x_i <= k.
  • Use a sliding window approach based on x-values since points are sorted.
  • A deque (monotonic queue) is well-suited to maintain potential candidates for (y_i + x_i) in decreasing order while ensuring the window constraint.
  • As you iterate through points, remove points that are outside the valid window and update the maximum answer accordingly.

Space and Time Complexity

Time Complexity: O(n) - Each point is processed once and each is added/removed from the deque at most once.
Space Complexity: O(n) - In the worst-case scenario, the deque can contain all points.

Solution

The solution involves the following steps:

  1. Transform the equation into a form where for each point j, you want to maximize (y_i + x_i) from a previous point i that satisfies x_j - x_i <= k.
  2. Use a deque to store indices (or the computed value along with x_i) such that the values (y_i + x_i) are maintained in decreasing order.
  3. For the current point j, first remove any points from the front of the deque that are no longer within the valid x-window (i.e., where x_j - x_i > k).
  4. If the deque is not empty, compute a candidate answer as (current y_j - current x_j) + (front value in deque) and update the maximum answer.
  5. Before moving to the next point, maintain the monotonicity of the deque by removing from the back any point whose (y_i + x_i) value is less than or equal to the current point’s value (y_j + x_j) as they will never be optimal for future points.
  6. Append the current point to the deque.
  7. Return the maximum answer found.

Code Solutions

# Python solution implementation with detailed comments.
from collections import deque

def findMaxValueOfEquation(points, k):
    # Initialize deque to store tuples of (x, y+x) in a monotonic decreasing order for y+x values.
    mono_deque = deque()
    max_value = float('-inf')
    
    # Iterate over each point in the sorted list
    for x, y in points:
        # Remove points from the front that are out of the window (x difference > k)
        while mono_deque and x - mono_deque[0][0] > k:
            mono_deque.popleft()
        
        # If deque is not empty, a candidate exists to maximize the equation.
        if mono_deque:
            # The candidate is the current point's (y-x) plus the maximum (y+x) from the deque front.
            max_value = max(max_value, y - x + mono_deque[0][1])
        
        # Prepare the current value for future comparisons
        current_value = y + x
        
        # Before appending the current point, pop from the back if current_value is greater
        while mono_deque and mono_deque[-1][1] <= current_value:
            mono_deque.pop()
        
        # Append the current point (store x and current value)
        mono_deque.append((x, current_value))
    
    return max_value

# Example usage:
# points = [[1,3],[2,0],[5,10],[6,-10]]
# k = 1
# print(findMaxValueOfEquation(points, k))  # Expected output: 4
← Back to All Questions