Show problems as
Classic problem #220HardArraySliding WindowSortingBucket SortOrdered Set

Contains Duplicate III

Real-world version: Close Samples Within a Short Window
Tracked in this browser only
Read Contains Duplicate III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tilt meter writes one signed sample per tick, given as samples, where samples[i] is the reading at tick i. An alarm fires when two different ticks i and j satisfy both of these:

  • the ticks are close in time: abs(i - j) <= indexSpan;
  • the readings are close in value: abs(samples[i] - samples[j]) <= valueSpan.

Both limits are inclusive, so a gap of exactly indexSpan ticks counts, and a value difference of exactly valueSpan counts. Readings may be negative, and valueSpan may be 0, in which case only two equal readings can fire the alarm.

Return true if such a pair of ticks exists, and false otherwise.

Examples

Example 1

Input
samples = [10, 100, 11], indexSpan = 2, valueSpan = 1
Output
true

Ticks 0 and 2 are 2 apart, which the time limit allows, and their readings 10 and 11 differ by 1, which the value limit allows.

Example 2

Input
samples = [10, 100, 11], indexSpan = 1, valueSpan = 1
Output
false

With the time limit at 1 tick, only the pairs (0, 1) and (1, 2) may be considered, and those readings differ by 90 and 89.

Example 3

Input
samples = [-7, -4], indexSpan = 1, valueSpan = 3
Output
true

The two ticks are 1 apart and their readings differ by exactly 3, which the inclusive value limit allows.

Constraints

  • 2 <= samples.length <= 10^5
  • -10^9 <= samples[i] <= 10^9
  • 1 <= indexSpan <= 10^5
  • indexSpan is at most samples.length.
  • 0 <= valueSpan <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def has_close_pair(samples: list[int], indexSpan: int, valueSpan: int) -> bool:
Java
public boolean hasClosePair(int[] samples, int indexSpan, int valueSpan)

More on the same topics