A conveyor belt carries n items past a scanner, and the belt's slots are numbered 0 through n-1 in the order they pass the scanner. The scanner records the integer barcode value carried by the item in each slot. A quality-control robot wants to grab three items -- from slots i < j < k -- that all carry the exact same barcode value, and it wants the grab to be as compact as possible: it measures compactness by the span k - i, the distance between the rightmost and leftmost of the three chosen slots (the middle slot j can be any slot strictly between them, as long as it also carries that barcode). Among every valid choice of three equal-barcode slots, find the smallest possible span. If no barcode value appears in at least three slots, no such triple exists.
The first line contains a single integer n, the number of slots on the belt.
The second line contains n space-separated integers barcode[0], barcode[1], ..., barcode[n-1], the barcode value scanned at each slot.
Print a single integer: the minimum span k - i over all triples of slots i < j < k with barcode[i] = barcode[j] = barcode[k]. If no barcode value occurs in three or more slots, print -1 instead.
Example 1
Input
7 1 2 3 2 1 2 1
Expected
4
Explanation
Barcode 1 appears at slots 0, 4 and 6 (span 6 - 0 = 6). Barcode 2 appears at slots 1, 3 and 5 (span 5 - 1 = 4). Barcode 3 appears only once, so it cannot form a triple. The smallest span among the valid triples is 4.
Example 2
Input
5 9 9 9 9 9
Expected
2
Explanation
Every slot carries barcode 9. Any three consecutive slots, such as 0, 1 and 2, form a valid triple with span 2 - 0 = 2, and no triple can have a smaller span, so the answer is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →