Far From Every Mark

Easy

A number line holds the points points and the marks marks. A point is far if its distance to every mark is strictly greater than gap, that is, |points[i] - marks[j]| > gap for all j. Return how many points in points are far. Equal points are counted separately.

Example 1

points=[2, 11, 20], marks=[9, 14, 25], gap=3 → 2

Point 2 is far from every mark (the nearest is 9, 7 away). Point 11 is close to 9 and 14. For point 20 the nearest marks are 14 and 25, 6 and 5 away, both more than 3. The answer is 2.

Example 2

points=[5, 5], marks=[5], gap=0 → 0

A distance of 0 is not greater than 0, so neither point counts as far.

Constraints

1 ≤ len(points), len(marks) ≤ 10⁵
-10⁴ ≤ points[i], marks[j] ≤ 10⁴
0 ≤ gap ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting

Similar problems

Values in Both Lists Easy Shared Values With Repeats Easy Best Pair Under the Limit Easy Twice as Much Easy Pairs Below the Limit Easy

Input

points=[2, 11, 20], marks=[9, 14, 25], gap=3

Expected

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