Best Pair of Close Beacons

Hard

Beacons stand along a straight road: beacons[i] = [x, y], where x is the beacon's position and y its brightness (which can be negative). The beacons are listed from left to right, with strictly increasing positions. The score of a pair of beacons i < j is y_i + y_j + (x_j − x_i). Only pairs at a distance x_j − x_i of at most reach count. Return the highest score among those pairs. At least one such pair is guaranteed to exist.

Example 1

beacons=[[0, 4], [2, -1], [3, 6], [10, 2]], reach=3 → 13

Pairs within 3: (0, 2) gives 4 − 1 + 2 = 5, (0, 3) gives 4 + 6 + 3 = 13, (2, 3) gives −1 + 6 + 1 = 6. The beacon at 10 is too far from the rest. The best is 13.

Example 2

beacons=[[-5, 1], [0, 0], [4, 9]], reach=4 → 13

The gap between −5 and 0 is 5, more than 4. That leaves one pair, (0, 4): 0 + 9 + 4 = 13.

Constraints

2 ≤ len(beacons) ≤ 10⁵
beacons[i] = [x, y]
-10⁸ ≤ x, y ≤ 10⁸
0 ≤ reach ≤ 2 · 10⁸
Positions x are strictly increasing
At least one pair of beacons is at most reach apart

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Sliding Window Monotonic Queue Heap (Priority Queue)

Similar problems

Moving Window Maximum Hard A Dark Gap Between Street Lamps Hard Shortest Stretch Reaching a Total Hard Maximum Sum With Short Hops Hard Longest Affordable Run of Machines Hard

Input

beacons=[[0, 4], [2, -1], [3, 6], [10, 2]], reach=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.