Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 105points[i].length == 2-108 <= xi, yi <= 1080 <= k <= 2 * 108xi < xj for all 1 <= i < j <= points.lengthxi form a strictly increasing sequence.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Sliding Window · Monotonic Queue
[[1,3],[2,0],[5,10],[6,-10]] 1
[[0,0],[3,0],[9,2]] 3
count-pairs-in-two-arrays)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1499: Max Value of Equation
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;
}
}
// Accepted solution for LeetCode #1499: Max Value of Equation
func findMaxValueOfEquation(points [][]int, k int) int {
ans := -(1 << 30)
hp := hp{}
for _, p := range points {
x, y := p[0], p[1]
for hp.Len() > 0 && x-hp[0].x > k {
heap.Pop(&hp)
}
if hp.Len() > 0 {
ans = max(ans, x+y+hp[0].v)
}
heap.Push(&hp, pair{y - x, x})
}
return ans
}
type pair struct{ v, x int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return a.v > b.v
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
# Accepted solution for LeetCode #1499: Max Value of Equation
class Solution:
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
ans = -inf
pq = []
for x, y in points:
while pq and x - pq[0][1] > k:
heappop(pq)
if pq:
ans = max(ans, x + y - pq[0][0])
heappush(pq, (x - y, x))
return ans
// Accepted solution for LeetCode #1499: Max Value of Equation
struct Solution;
use std::collections::VecDeque;
impl Solution {
fn find_max_value_of_equation(points: Vec<Vec<i32>>, k: i32) -> i32 {
let n = points.len();
let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
let mut res = std::i32::MIN;
for j in 0..n {
let xj = points[j][0];
let yj = points[j][1];
while let Some(&(_, xi)) = queue.front() {
if xi + k < xj {
queue.pop_front();
} else {
break;
}
}
if let Some(&(diff, _)) = queue.front() {
res = res.max(diff + yj + xj);
}
while let Some(&(diff, xi)) = queue.back() {
if (diff, xi) < (yj - xj, xj) {
queue.pop_back();
} else {
break;
}
}
queue.push_back((yj - xj, xj));
}
res
}
}
#[test]
fn test() {
let points = vec_vec_i32![[1, 3], [2, 0], [5, 10], [6, -10]];
let k = 1;
let res = 4;
assert_eq!(Solution::find_max_value_of_equation(points, k), res);
let points = vec_vec_i32![[0, 0], [3, 0], [9, 2]];
let k = 3;
let res = 3;
assert_eq!(Solution::find_max_value_of_equation(points, k), res);
}
// Accepted solution for LeetCode #1499: Max Value of Equation
function findMaxValueOfEquation(points: number[][], k: number): number {
let ans = -(1 << 30);
const pq = new Heap<[number, number]>((a, b) => b[0] - a[0]);
for (const [x, y] of points) {
while (pq.size() && x - pq.top()[1] > k) {
pq.pop();
}
if (pq.size()) {
ans = Math.max(ans, x + y + pq.top()[0]);
}
pq.push([y - x, x]);
}
return ans;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class Heap<T = number> {
data: Array<T | null>;
lt: (i: number, j: number) => boolean;
constructor();
constructor(data: T[]);
constructor(compare: Compare<T>);
constructor(data: T[], compare: Compare<T>);
constructor(data: T[] | Compare<T>, compare?: (lhs: T, rhs: T) => number);
constructor(
data: T[] | Compare<T> = [],
compare: Compare<T> = (lhs: T, rhs: T) => (lhs < rhs ? -1 : lhs > rhs ? 1 : 0),
) {
if (typeof data === 'function') {
compare = data;
data = [];
}
this.data = [null, ...data];
this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0;
for (let i = this.size(); i > 0; i--) this.heapify(i);
}
size(): number {
return this.data.length - 1;
}
push(v: T): void {
this.data.push(v);
let i = this.size();
while (i >> 1 !== 0 && this.lt(i, i >> 1)) this.swap(i, (i >>= 1));
}
pop(): T {
this.swap(1, this.size());
const top = this.data.pop();
this.heapify(1);
return top!;
}
top(): T {
return this.data[1]!;
}
heapify(i: number): void {
while (true) {
let min = i;
const [l, r, n] = [i * 2, i * 2 + 1, this.data.length];
if (l < n && this.lt(l, min)) min = l;
if (r < n && this.lt(r, min)) min = r;
if (min !== i) {
this.swap(i, min);
i = min;
} else break;
}
}
clear(): void {
this.data = [null];
}
private swap(i: number, j: number): void {
const d = this.data;
[d[i], d[j]] = [d[j], d[i]];
}
}
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.