#154EasyArrays & Hashing· Distance-Bounded Duplicates

Nearby Duplicate Orders

An online shop receives a stream of order ids. A double click on the "Pay" button sends the same id twice within a short burst, and the fraud rules flag any id that shows up again within `k` positions of its previous appearance. Given the array `orders` and the integer `k`, return `true` if there exist two different indices `i < j` with `orders[i] == orders[j]` and `j - i <= k`, and `false` otherwise. With `k = 0` nothing can be flagged because two different positions are at least one apart.

Input format

`orders`: an array of integers; `k`: a non-negative integer.

Output format

`true` if some value repeats within distance `k`, otherwise `false`.

Examples

Input: orders = [4, 9, 4], k = 2

Output: true

The value 4 appears at indices 0 and 2, which are 2 apart, and 2 <= k.

Input: orders = [4, 9, 4], k = 1

Output: false

The two 4s are 2 apart but only a distance of 1 is allowed.

Input: orders = [1, 2, 3, 1, 2, 3], k = 2

Output: false

Every repeated value is three positions away from its twin, which is more than k = 2.

Constraints

1 <= orders.length <= 10^5
0 <= orders[i] <= 10^9
0 <= k <= 10^5

Study first

#hash-table
#sliding-window
#arrays