k-Amazing Numbers (Codeforces 1417C)
Tags: Others, data structures

You are given an array $$$a$$$ consisting of $$$n$$$ integers numbered from $$$1$$$ to $$$n$$$.Let's define the $$$k$$$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $$$k$$$ (recall that a subsegment of $$$a$$$ of length $$$k$$$ is a contiguous part of $$$a$$$ containing exactly $$$k$$$ elements). If there is no integer occuring in all subsegments of length $$$k$$$ for some value of $$$k$$$, then the $$$k$$$-amazing number is $$$-1$$$.For each $$$k$$$ from $$$1$$$ to $$$n$$$ calculate the $$$k$$$-amazing number of the array $$$a$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of elements in the array. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case print $$$n$$$ integers, where the $$$i$$$-th integer is equal to the $$$i$$$-amazing number of the array.


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

Sample Outputs:
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1

Solution (Python):
import math
import sys

class Read:

    @staticmethod
    def string():
        return input()

    @staticmethod
    def int():
        return int(input())

    @staticmethod
    def list(sep=' '):
        return input().split(sep)

    @staticmethod
    def list_int(sep=' '):
        return list(map(int, input().split(sep)))

def solve():
    n = Read.int()
    a = Read.list_int()
    tmp = {}
    last = {}
    for i in range(n):
        v = i
        if a[i] in last:
            v = i - last[a[i]] - 1
        last[a[i]] = i
        if a[i] in tmp:
            if v > tmp[a[i]]:
                tmp[a[i]] = v
        else:
            tmp[a[i]] = v
    for (k, v) in last.items():
        v = n - 1 - v
        if v > tmp[k]:
            tmp[k] = v
    tmp_s = sorted(list(tmp.keys()))
    res = []
    l = 0
    for i in tmp_s:
        r = n - tmp[i]
        for j in range(l, r):
            res.append(str(i))
        if r > l:
            l = r
    for i in range(n - len(res)):
        res.append('-1')
    res.reverse()
    print(' '.join(res))
query_count = Read.int()
while query_count:
    query_count -= 1
    solve()

Solution (Python):
def func(n, a):
    c = [-1] * (n + 1)
    f = [0] * (n + 1)
    indices = [[] for _ in range(n + 1)]
    for i in range(n):
        indices[a[i]].append(i + 1)
    for i in range(1, n + 1):
        lis = indices[i]
        if lis != []:
            m = max(lis[0], n - lis[-1] + 1)
            for j in range(1, len(lis)):
                m = max(m, lis[j] - lis[j - 1])
            f[i] = m
    for i in range(1, n + 1):
        m = f[i]
        if m != 0:
            while m < n + 1 and c[m] == -1:
                c[m] = i
                m += 1
    return c[1:]
if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        brr = func(n, arr)
        print(' '.join(list(map(str, brr))))

Solution (Python):
def amazing_numbers(n, arr):
    occur_lis = [[] for i in range(n + 1)]
    for index in range(n):
        a = arr[index]
        occur_lis[a].append(index + 1)
    f = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        lis = occur_lis[i]
        if lis != []:
            m = max(lis[0], n - lis[-1] + 1)
            for j in range(len(lis) - 1):
                m = max(m, lis[j + 1] - lis[j])
            f[i] = m
    ans = [-1 for i in range(n + 1)]
    for i in range(1, n + 1):
        if f[i] != 0:
            p = f[i]
            while p < n + 1 and ans[p] == -1:
                ans[p] = i
                p += 1
    return ans[1:]
if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        brr = amazing_numbers(n, arr)
        print(' '.join(list(map(str, brr))))