Repeat Within Reach

EasySliding Window

Problem

A fraud filter flags a card when the same merchant ID appears twice within a short span of transactions. Given the merchant IDs nums in order and a reach k, decide whether there exist two positions i < j with nums[i] == nums[j] and j - i ≤ k.

Return true if such a pair exists, otherwise false.

Example 1

Input:
nums = [4, 1, 7, 4], k = 3
Output:
true

The two 4s are at positions 0 and 3, exactly 3 apart.

Example 2

Input:
nums = [4, 1, 7, 4], k = 2
Output:
false

The only repeated value is 3 positions apart, more than 2.

Example 3

Input:
nums = [2, 2], k = 0
Output:
false

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9
  • 0 ≤ k ≤ 10^5

Hint

Show the first hint

For position j, which earlier positions could form a valid pair with it?

Walkthrough

How to approach it

01Clarify before coding

  • Is the distance condition inclusive? Yes, j - i ≤ k.
  • Can k be 0? Yes; then no pair can qualify because i < j forces a distance of at least 1.
  • Can k exceed the array length? Yes; then any duplicate at all qualifies.

02Brute force

For each i, compare nums[i] with the next k elements.

Cost: O(n·min(n, k)) time; with n = k = 10^5 that is about 5·10^9 comparisons.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.