Max Value of Equation - Practice Coding Problems

Max Value of Equation - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1

› Output: 4

💡 Note: The first two points satisfy |1 - 2| <= 1. The equation value is 3 + 0 + |1 - 2| = 4.

Example 2 — Multiple Valid Pairs

$ Input: points = [[0,0],[3,0],[9,2]], k = 3

› Output: 3

💡 Note: Points [0,0] and [3,0] satisfy |0 - 3| <= 3. The equation value is 0 + 0 + |0 - 3| = 3.

Example 3 — Larger Distance

$ Input: points = [[-17,-15],[-10,3],[2,15]], k = 12

› Output: 16

💡 Note: Points [-10,3] and [2,15] satisfy |(-10) - 2| <= 12. The equation value is 3 + 15 + |(-10) - 2| = 30. But points [-17,-15] and [-10,3] give (-15) + 3 + |(-17) - (-10)| = 16.

Constraints

2 ≤ points.length ≤ 10⁵
points[i].length == 2
-10⁸ ≤ points[i][0], points[i][1] ≤ 10⁸
0 ≤ k ≤ 2 × 10⁸
points[i][0] < points[j][0] for all 1 ≤ i < j ≤ points.length

Visualization

Tap to expand

Understanding the Visualization

Input

Points sorted by x-coordinate and distance limit k

Find Pairs

Identify all valid pairs where |xi - xj| ≤ k

Calculate Maximum

Compute yi + yj + |xi - xj| and return maximum

Key Takeaway

🎯 Key Insight: Transform equation to (yi - xi) + (yj + xj) and use monotonic deque for O(n) solution

Asked in

G Google 28 a Amazon 15

The key insight is to transform the equation yi + yj + |xi - xj| into (yi - xi) + (yj + xj) since points are sorted by x-coordinate. This allows us to use a monotonic deque to efficiently maintain the maximum (yi - xi) value for all valid previous points within distance k. Best approach uses sliding window with deque for O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Monotonic Deque	O(n)	O(n)	Use a deque to maintain the best candidates in a sliding window
Brute Force	O(n²)	O(1)	Check all valid pairs of points

Sliding Window with Monotonic Deque — Algorithm Steps

Transform equation to separate terms by point index
Use deque to maintain candidates sorted by (yi - xi) in descending order
For each point j, remove invalid points from deque front
Calculate value using deque front + (yj + xj)
Add current point to deque back

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Rewrite equation as (yi - xi) + (yj + xj)

Deque Window

Maintain points within distance k, sorted by (yi - xi)

Optimal Pair

Use deque front (best yi - xi) with current point

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int points[][2], int n, int k) {
    int dq[1000]; // Simple array as deque
    int front = 0, back = 0;
    int maxValue = INT_MIN;
    
    for (int j = 0; j < n; j++) {
        int xj = points[j][0], yj = points[j][1];
        
        // Remove points outside window
        while (front < back && xj - points[dq[front]][0] > k) {
            front++;
        }
        
        // Calculate value using best previous point
        if (front < back) {
            int i = dq[front];
            int xi = points[i][0], yi = points[i][1];
            int value = (yi - xi) + (yj + xj);
            if (value > maxValue) {
                maxValue = value;
            }
        }
        
        // Maintain monotonic property
        int currentVal = yj - xj;
        while (front < back && (points[dq[back-1]][1] - points[dq[back-1]][0]) <= currentVal) {
            back--;
        }
        
        dq[back++] = j;
    }
    
    return maxValue;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse points array
    int points[1000][2];
    int n = 0;
    char *ptr = line + 1;
    
    while (*ptr && n < 1000) {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            points[n][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            n++;
        }
        ptr++;
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(points, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each point is added and removed from deque at most once

✓ Linear Growth

Space Complexity

O(n)

Deque can store up to n points in worst case

⚡ Linearithmic Space

31.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Monotonic Deque — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler