Two Nets on a Line

Medium

Fish are frozen on a number line: positions[i] is the coordinate of fish i. The array is sorted in non-decreasing order, and several fish may share a point. You cast two nets. Each net is a segment [a, a + width] with integer endpoints; a fish is caught if its coordinate lies in at least one of the two segments (endpoints included). The nets may overlap. Return the largest number of fish you can catch.

Example 1

positions=[2, 3, 3, 7, 8, 12, 13, 14], width=1 → 5

The net [2, 3] covers three fish, and the net [7, 8] (or [12, 13]) covers two more. That is 5.

Example 2

positions=[4, 4, 4], width=0 → 3

A zero-width net placed at 4 already catches all three fish.

Example 3

positions=[1, 5, 9, 20, 21], width=4 → 4

Constraints

1 ≤ len(positions) ≤ 10⁵
1 ≤ positions[i] ≤ 10⁹
positions is sorted in non-decreasing order
0 ≤ width ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Nearest k Values Medium Windows With a Small Product Medium Longest Shared Run Medium Longest Run of Ones With k Fixes Medium

Input

positions=[2, 3, 3, 7, 8, 12, 13, 14], width=1

Expected

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