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.
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: