Tóm tắt đề bài

Cho mảng ~a~ gồm ~n~ phần tử. Hãy tìm khoảng cách ngắn nhất giữa mọi cặp phần tử bằng nhau trong mảng. Nói cách khác, hãy tìm ~min~ ~(|i - j|)~ với mọi ~1 \le i < j \le n~ và ~a_i = a_j~.

Subtask 1. ~n \le 10^3~

Sử dụng hai vòng lặp, nếu ~a_i = a_j~ thì cập nhật kết quả với ~|i - j|~.

Độ phức tạp: ~O~ (~n^2~).

Subtask 2. ~n \le 10^5~

Nhận xét: Với mọi ~a_j~ ta cần quan tâm tới ~a_i = a_j~ và với ~i~ lớn nhất có thể.

Vì vậy, trong quá trình duyệt, ta sẽ lưu vị trí sau cùng ta gặp phần tử có giá trị là ~x~ nào đó. Điều này có thể thực hiện với ~map~. Hoặc cũng có thể nén số lại do ta chỉ quan tâm tính lớn bé của các phần tử, sau đó sử dụng mảng đánh dấu.

Độ phức tạp: ~O~ (~n \times log~ ~n~).