973. Best Equation Value
Sensors are placed along a straight pipeline, and engineers want to pick two of them to cross-calibrate. The list points holds [x, y] for each sensor, already sorted by x with all x values different. For two sensors i < j whose positions satisfy |xi - xj| <= k, their pairing value is yi + yj + |xi - xj|.
A sensor cannot be paired with itself, and a pair is counted once. Return the maximum pairing value over all such pairs; the value may be negative. The input guarantees at least one pair of sensors is within distance k of each other.
Example 1
- Input:
- points = [[0,4],[3,-2],[4,6],[9,1]], k = 4
- Output:
- 14
- Explanation:
The best pair is the points at x = 0 and x = 4: their distance 4 is allowed and the value is 4 + 6 + 4 = 14; the point at x = 9 is too far from everything.
Example 2
- Input:
- points = [[-5,2],[-1,2],[2,-3]], k = 10
- Output:
- 8
- Explanation:
All three points are within distance 10 of each other; the pair at x = -5 and x = -1 gives 2 + 2 + 4 = 8, better than the other pairs (2 and 6).
Constraints
- 2 ≤ points.length ≤ 105
- points[i].length == 2
- -108 ≤ xi, yi ≤ 108
- xi < xj for all 0 ≤ i < j
- 0 ≤ k ≤ 2 * 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)