Official

E - Shortest Duplicate Subarray Editorial by en_translator


First, we consider the following modified problem: replace “that has a repeated value, occurring multiple times in \(A\)” with “where the value \(1\) occurs multiple times.”

This can be solved by sorting indices \(i\) with \(A_i=1\) in ascending order and finding differences between adjacent terms.

The same procedure can be applied for values other than \(1\). By dividing the indices into groups firsthand, the problem has been solved in a total of \(O(N)\) time.

Sample code (Python3)

N = int(input())
A = list(map(int, input().split()))

ans = N + 1
pos = [[] for _ in range(1_000_001)]

for i in range(N):
    pos[A[i]].append(i)

for i in range(1_000_001):
    if len(pos[i]) < 2:
        continue
    for j in range(len(pos[i]) - 1):
        ans = min(ans, pos[i][j + 1] - pos[i][j] + 1)

if ans == N + 1:
    print(-1)
else:
    print(ans)

Bonus

The problem can be solved with so-called sliding window trick.

posted:
last update: