Max Value Of Equation - Leetcode Solution

The Max Value of Equation problem on LeetCode asks us to find the maximum value of a given equation of the form yi + yj + |xi - xj|, where 0 <= i < j < n and x and y are given arrays of n integers.

The solution to this problem involves using a sliding window approach along with a monotonic queue to efficiently compute the maximum value of the equation.

Algorithm:

1. Initialize a monotonic queue q and a variable ans to store the maximum value.
2. For each i from 0 to n-1, do the following: a. Remove all indices from the front of the queue that are more than k positions away from i. This is because these indices cannot be paired with i to form a valid pair since the difference in their x values will be greater than k. b. If the queue is not empty, compute the current value of the equation for the pair (i, q.front()) and update ans if it is greater than the current max value. c. Remove all indices from the back of the queue that have a lower value of y than y[i] since they cannot form a valid pair with any future index. d. Insert the current index i into the queue.
3. Return the value of ans.

Pseudo-code:

ans = -INF
q = deque()

for i in range(n):
    # Step 2a
    while q and i - q[0][0] > k:
        q.popleft()
    
    # Step 2b
    if q:
        j = q[0][1]
        ans = max(ans, y[i] + y[j] + (x[i] - x[j]))
    
    # Step 2c
    while q and y[i] >= y[q[-1][1]]:
        q.pop()
    
    # Step 2d
    q.append((i, y[i]))
    
return ans

Time Complexity: O(n) since we do a constant amount of work for each element in the array.

Space Complexity: O(k) since the size of the queue can be at most k at any point.

1