Show problems as
Classic problem #219EasyArrayHash TableSliding Window

Contains Duplicate II

Real-world version: Nearby Repeat Trim
Tracked in this browser only
Read Contains Duplicate II on LeetCode(opens in a new tab)

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

A lathe operator keeps a trim log. trims[i] is the signed correction, in micrometres, that was dialled in before pass i: a negative figure pulls the cut back, a positive figure pushes it forward, and 0 means the pass ran with the dial untouched.

Quality control cares about corrections that come back around quickly, because a value reused soon after its last use points at a machine that is drifting rather than settling. You are given the log and an integer span.

Report whether some correction figure was dialled in on two separate passes whose pass numbers are no more than span apart. Return true when such a pair of passes exists and false when none does. A pass is never a repeat of itself, so a span of 0 can only ever give false.

Examples

Example 1

Input
trims = [4, -2, 7, -2, 9], span = 2
Output
true

The correction -2 was dialled in before pass 1 and again before pass 3, and those passes sit 2 apart, which the span allows.

Example 2

Input
trims = [5, -3, 5], span = 1
Output
false

Only the figure 5 was reused, on passes 0 and 2. Those passes are 2 apart, so with a span of 1 the log counts as settled.

Example 3

Input
trims = [8, -1, 3, 8], span = 3
Output
true

The reused figure 8 sits on the first and last passes, exactly 3 apart, so the final pass still has to be weighed against the whole span behind it.

Constraints

  • 1 <= trims.length <= 10^5
  • -10^9 <= trims[i] <= 10^9
  • 0 <= span <= 10^5

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_nearby_repeat(trims: list[int], span: int) -> bool:
Java
public boolean hasNearbyRepeat(int[] trims, int span)

More on the same topics