Dominated Subarray (Codeforces 1257C)
Tags: Greedy, two pointers

Let's call an array $$$t$$$ dominated by value $$$v$$$ in the next situation.At first, array $$$t$$$ should have at least $$$2$$$ elements. Now, let's calculate number of occurrences of each number $$$num$$$ in $$$t$$$ and define it as $$$occ(num)$$$. Then $$$t$$$ is dominated (by $$$v$$$) if (and only if) $$$occ(v) > occ(v')$$$ for any other number $$$v'$$$. For example, arrays $$$[1, 2, 3, 4, 5, 2]$$$, $$$[11, 11]$$$ and $$$[3, 2, 3, 2, 3]$$$ are dominated (by $$$2$$$, $$$11$$$ and $$$3$$$ respectevitely) but arrays $$$[3]$$$, $$$[1, 2]$$$ and $$$[3, 3, 2, 2, 1]$$$ are not.Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.You are given array $$$a_1, a_2, \dots, a_n$$$. Calculate its shortest dominated subarray or say that there are no such subarrays.The subarray of $$$a$$$ is a contiguous part of the array $$$a$$$, i. e. the array $$$a_i, a_{i + 1}, \dots, a_j$$$ for some $$$1 \le i \le j \le n$$$.

Input: The first line contains single integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases. Each test case consists of two lines.The first line contains single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the corresponding values of the array $$$a$$$.It's guaranteed that the total length of all arrays in one test doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print $$$T$$$ integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or $$$-1$$$ if there are no such subarrays.

Note: In the first test case, there are no subarrays of length at least $$$2$$$, so the answer is $$$-1$$$.In the second test case, the whole array is dominated (by $$$1$$$) and it's the only dominated subarray.In the third test case, the subarray $$$a_4, a_5, a_6$$$ is the shortest dominated subarray.In the fourth test case, all subarrays of length more than one are dominated.

Sample Inputs:
4
1
1
6
1 2 3 4 5 1
9
4 1 2 4 5 4 3 2 1
4
3 3 3 3

Sample Outputs:
-1
6
3
2

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    min_length = float('inf')
    last_index = {}
    for i in range(n):
        a = l[i]
        if a in last_index:
            min_length = min(min_length, i - last_index[a])
        last_index[a] = i
    if min_length == float('inf'):
        print(-1)
    else:
        print(min_length + 1)

Solution (Python):
t = int(input())
for i in range(t):
    n = int(input())
    x = list(map(int, input().split()))
    d = [-1] * (n + 5)
    res = n + 1
    for j in range(n):
        if d[x[j]] > -1:
            res = min(res, j - d[x[j]] + 1)
        d[x[j]] = j
    if res == n + 1:
        print(-1)
    else:
        print(res)

Solution (Python):
def dominatedSubarray(array: list):
    position = [-1] * len(array)
    dominated = float('inf')
    for i in range(len(array)):
        if position[array[i] - 1] != -1:
            dominated = min(dominated, i + 1 - position[array[i] - 1])
        position[array[i] - 1] = i
    print('-1') if dominated == float('inf') else print(dominated)
if __name__ == '__main__':
    for i in range(int(input())):
        input()
        dominatedSubarray(list(map(int, input().split(' '))))