Max value of equation

Array Queue Sliding Window Heap (Priority Queue) Monotonic Queue

45.0% acceptance

Feb 25, 2026

1411

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn find_max_value_of_equation(points: Vec<Vec<i32>>, k: i32) -> i32 {
    // maximize: (yj + xj) + (yi - xi) for xi in [xj-k, xj)
    let mut deque: VecDeque<(i32, i32)> = VecDeque::new(); // (x, y-x)
    let mut ans = i32::MIN;
    for p in &points {
      let (xj, yj) = (p[0], p[1]);
      // Remove points out of range
      while let Some(&(xi, _)) = deque.front() {
        if xj - xi > k { deque.pop_front(); } else { break; }
      }
      if let Some(&(_, yi_xi)) = deque.front() {
        ans = ans.max(yj + xj + yi_xi);
      }
      // Maintain deque in decreasing order of yi-xi
      let val = yj - xj;
      while let Some(&(_, back_val)) = deque.back() {
        if back_val <= val { deque.pop_back(); } else { break; }
      }
      deque.push_back((xj, val));
    }
    ans
  }
}