Repeated order inside k arrivals

Scenario

Kestrel Shop receives orders in a queue, in the order they arrive. When the network is slow, a checkout page may retry and submit the same order twice in quick succession. A retry carries the same order id as the original.

The payments-safety team wants to stop double charges before they happen. They flag an order id that arrives again within k arrivals of its previous arrival. The team stops the queue at the first flagged arrival and reviews it. An id that returns much later is outside the retry window, so it is not flagged.

Your task

Write first_repeat_within(orders, k).

orders[j] is the id of the order that arrived at position j of the queue.
Arrival j is flagged when some earlier arrival i has the same id and j - i ≤ k.
Return the smallest flagged index j: the first arrival where the queue must stop.
Return the position of the repeat, j, not the position of the earlier copy, i.
If no arrival is flagged, return -1.
k may be larger than the number of orders. Then every earlier arrival is in range.

Examples

Example 1 (traced)#

text2 lines

Input:  orders = [4, 8, 1, 4, 6, 1, 6], k = 2
Output: 6

j	Order id	Leaves the window	Window before the check	Repeat inside?
0	4	none	empty	no
1	8	none	4	no
2	1	none	4, 8	no
3	4	4	8, 1	no
4	6	8	1, 4	no
5	1	1	4, 6	no
6	6	4	6, 1	yes

Id 4 returns at position 3, three arrivals after its first copy, so it is not flagged. Id 6 returns at position 6, exactly two arrivals after position 4, so the queue stops there.

Example 2#

text2 lines

Input:  orders = [5, 2, 5, 9, 9], k = 3
Output: 2

The two 9s are closer together, but the repeat of 5 at position 2 comes first.

Example 3#

text2 lines

Input:  orders = [10, 20, 30], k = 5
Output: -1

k is larger than the queue, so every earlier arrival is in range. No id repeats.

Constraints

1 ≤ orders.length ≤ 10^5
1 ≤ orders[i] ≤ 10^9 (order ids are identifiers, not amounts)
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

Comparing each arrival with the k arrivals before it costs up to about n × k comparisons. With n = k = 10^5 and no repeats, that is about 5 × 10^9: far over the budget of about 10^8 simple operations a second. Aim for O(n).

The ids go up to 10^9, so an array indexed by id would be far too large. A hash set holds only the ids that are in the window.

Scenario

Your task

Write first_repeat_within(orders, k).

orders[j] is the id of the order that arrived at position j of the queue.
Arrival j is flagged when some earlier arrival i has the same id and j - i ≤ k.
Return the smallest flagged index j: the first arrival where the queue must stop.
Return the position of the repeat, j, not the position of the earlier copy, i.
If no arrival is flagged, return -1.
k may be larger than the number of orders. Then every earlier arrival is in range.

Examples

Example 1 (traced)#

text2 lines

Input:  orders = [4, 8, 1, 4, 6, 1, 6], k = 2
Output: 6

j	Order id	Leaves the window	Window before the check	Repeat inside?
0	4	none	empty	no
1	8	none	4	no
2	1	none	4, 8	no
3	4	4	8, 1	no
4	6	8	1, 4	no
5	1	1	4, 6	no
6	6	4	6, 1	yes

Id 4 returns at position 3, three arrivals after its first copy, so it is not flagged. Id 6 returns at position 6, exactly two arrivals after position 4, so the queue stops there.

Example 2#

text2 lines

Input:  orders = [5, 2, 5, 9, 9], k = 3
Output: 2

The two 9s are closer together, but the repeat of 5 at position 2 comes first.

Example 3#

text2 lines

Input:  orders = [10, 20, 30], k = 5
Output: -1

k is larger than the queue, so every earlier arrival is in range. No id repeats.

Constraints

1 ≤ orders.length ≤ 10^5
1 ≤ orders[i] ≤ 10^9 (order ids are identifiers, not amounts)
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

The ids go up to 10^9, so an array indexed by id would be far too large. A hash set holds only the ids that are in the window.