Close Values Far Apart

Medium

You are given an integer array values and an integer gap. Choose two elements whose positions are at least gap apart, that is indices i and j with |i - j| ≥ gap, so that |values[i] - values[j]| is as small as possible. Return that smallest value.

Example 1

values=[9, 2, 14, 7, 3], gap=3 → 1

The allowed position pairs are (0, 3), (0, 4) and (1, 4). The best is 2 and 3 at positions 1 and 4, a difference of 1.

Example 2

values=[10, 30, 11], gap=2 → 1

The only pair is 10 and 11, a difference of 1.

Example 3

values=[20, 3, 17], gap=1 → 3

Constraints

2 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
1 ≤ gap < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Ordered Set

Similar problems

Low, Peak, Middle Medium One Edit to the Closest Match Medium Ones Outnumber Zeros Medium Rank of an Arrangement Medium Leftmost Locker That Fits Medium

Input

values=[9, 2, 14, 7, 3], gap=3

Expected

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