Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

The Smallest Window II

  For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $K$, find the smallest sub-array size (smallest window length) where the elements in the sub-array contains all integers in range [$1, 2, ..., K$]. If there is no such sub-array, report 0.

Constraints

 $1 \leq N \leq 10^5$ 

 $1 \leq K \leq 10^5$

 $1 \leq a_i \leq 10^5$

Input

The input is given in the following format.

$N$ $K$

$a_1$ $a_2$ ... $a_N$

Output

  Print the smallest sub-array size in a line.

Sample Input 1

6 2
4 1 2 1 3 5

Sample Output 1

2

Sample Input 2

6 3
4 1 2 1 3 5

Sample Output 2

3

Sample Input 3

3 4
1 2 3

Sample Output 3

0



Sample input:
6 2
4 1 2 1 3 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
cnts = [0] * (k + 1)
ans = 1e6
existing = 0
r = 0
for l in range(n - k):
    while r < n and existing < k:
        a = aa[r]
        if a <= k:
            cnts[a] += 1
            if cnts[a] == 1:
                existing += 1
        r += 1
    ans = min(ans, r - l)
    a = aa[l]
    if a <= k:
        cnts[a] -= 1
        if cnts[a] == 0:
            existing -= 1

print(ans if ans < 1e6 else 0)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
cnts = [0] * (k + 1)
ans = 1e6
existing = 0
r = 0
for l in range(n - k + 1):
    while r < n and existing < k:
        a = aa[r]
        if a <= k:
            cnts[a] += 1
            if cnts[a] == 1:
                existing += 1
        r += 1
    ans = min(ans, r - l)
    a = aa[l]
    if a <= k:
        cnts[a] -= 1
        if cnts[a] == 0:
            existing -= 1

print(ans if ans < 1e6 else 0)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
aa = list(map(int, input().split()))
cnts = [0] * (k + 1)
ans = 1e6
existing = 0
r = 0
for l in range(n - k + 1):
    while r < n and existing < k:
        a = aa[r]
        if a <= k:
            cnts[a] += 1
            if cnts[a] == 1:
                existing += 1
        r += 1
    if k == existing:
        ans = min(ans, r - l)
    a = aa[l]
    if a <= k:
        cnts[a] -= 1
        if cnts[a] == 0:
            existing -= 1

print(ans if ans < 1e6 else 0)

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

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

res = N + 1
st = SegmentTree([0] * K)
rt = 0

for lt in range(N):
    while rt < N and st.tree[1] == 0:
        if A[rt] <= K:
            st.set(A[rt] - 1, st.query(A[rt] - 1, A[rt]) + 1)
        rt += 1
    if st.tree[1] != 0:
        res = min(res, rt - lt)
    if A[lt] <= K:
        st.set(A[lt] - 1, st.query(A[lt] - 1, A[lt]) - 1)

print(res if res <= N else 0)

Submission status: Accepted

Solution code:
import sys

n,k = map(int, input().split( ))
a = list(map(int, input().split( )))
tmp = max(a)
tmp2 = max(tmp,n,k)+1
chk = [0]*(tmp2)

for i in range(n):
    chk[a[i]] += 1

if 0 in chk[1:k+1]:
    print(0)
    sys.exit()

right = n-1
left = 0
L = []

while right < n:
    while chk[a[right]] > 1 or a[right] > k:
        chk[a[right]] -= 1
        right -= 1
        
    ln = right - left + 1
    L.append(ln)
    
    while chk[a[left]] > 1 or a[left] > k:
        chk[a[left]] -= 1
        left += 1
    ln = right - left + 1
    L.append(ln)
    chk[a[left]] -= 1
    left += 1
    while chk[a[left-1]] == 0:
        right += 1
        if right >= n:
            break
        chk[a[right]] += 1
    ln = right -left +1
    L.append(ln)
print(min(L))

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, K = map(lambda x: int(x), input().split())
    a = list(map(lambda x: int(x), input().split()))

    ans = N + 1
    idx = 0
    num = 0
    values = [0] * K
    for s in range(N):
        while (idx < N and num < K):
            v = a[idx]
            if (v <= K):
                values[v - 1] += 1
                if (1 == values[v - 1]):
                    num += 1
            idx += 1
        if (K == num):
            ans = min(ans, idx - s)
        v = a[s]
        if (v <= K):
            values[v - 1] -= 1
            if (0 == values[v - 1]):
                num -= 1
    ans = ans if ans < N + 1 else 0
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Sliding Window - The Smallest Window II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_B&lang=jp

"""
from collections import defaultdict

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

left, right, num = 0, 0, 0
ans = float('inf')
count = defaultdict(int)
while True:
    while right < N and num < K:
        if count[A[right]] == 0 and A[right] <= K:
            num += 1
        count[A[right]] += 1
        right += 1
    if num < K:
        break
    ans = min(ans, right - left)
    if count[A[left]] == 1 and A[left] <= K:
        num -= 1
    count[A[left]] -= 1
    left += 1
print(ans if ans != float('inf') else 0)

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def LIR(n): return [LI() for i in range(n)]
def MI(): return map(int, input().split())
#1:set
#1_A
"""
n,q = map(int, input().split(" "))
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] = group[key[x]] + group[key[y]]
            for j in group[v]:
                key[j] = key[x]
            group[v] = []
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
"""
#1_B
"""
def root(x,n):
    if par[x][0] == x:
        return [x,n+par[x][1]]
    return root(par[x][0],par[x][1])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx[0] == ry[0]:
        return
    par[rx][0] = ry[0]
    par[rx][1] += ry[1]
n,q = map(int, input().split(" "))
par = [[i,0] for i in range(n)]
for i in range(q):
    q = list(map(int, input().split(" ")))
    if q[0] == 0:

        if root(q[1],0) != root(q[])
"""
#2:range quary
#2_A
"""
n,q = map(int, input().split(" "))
k = 2**31-1
a = [float("inf") for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split(" "))
    if com == 0:
        a[x] = y
    else:
        mi = k
        for j in range(x, y+1):
            if a[j] == float("inf"):
                mi = min(mi, k)
            else:
                mi = min(mi,a[j])
        print(mi)
"""
#2_B

#2_C

#2_D

#2_E

#2_F

#2_G

#2_H

#2_I


#3:sliding window
#3_A
"""
n,s = MI()
a = LI()
for i in range(1,n):
    a[i] += a[i-1]
a.insert(0,0)
l = 0
r = 0
ans = float("inf")
if a[1] >= s:
    print(1)
    quit()
while r < n:
    r += 1
    if a[r]-a[l] >= s:
        while a[r]-a[l] >= s and l < r:
            l += 1
        ans = min(ans, r-l+1)
if ans == float("inf"):
    print(0)
    quit()
print(ans)
"""
#4:coordinate compression
n,k = MI()
a = LI()
l = 0
r = 0
ans = float("inf")
fl = [0 for i in range(k+1)]
s = 0
if k == 1 and a[0] == 1:
    print(1)
    quit()
if a[0] <= k:
    fl[a[0]] = 1
    s = 1
while r < n-1:
    r += 1
    if a[r] <= k:
        if not fl[a[r]]:
            s += 1
        fl[a[r]] += 1
    if s == k:
        while s == k:
            l += 1
            if a[l-1] <= k:
                if fl[a[l-1]] == 1:
                    s -= 1
                fl[a[l-1]] -= 1
        ans = min(ans, r-l+2)
if ans == float("inf"):
    print(0)
    quit()
print(ans)


#5:comulative sum
#5_A
"""
n,t = map(int, input().split(" "))
num = [0 for i in range(t)]
for i in range(n):
    l,r = map(int, input().split(" "))
    num[l] += 1
    if r < t:
        num[r] -= 1
for i in range(1,t):
    num[i] += num[i-1]
print(max(num))
"""

#5_B
"""
n = int(input())
lec = [[0 for i in range(1001)] for j in range(1001)]
max_x = 0
max_y = 0
for i in range(n):
    x,y,s,t = map(int, input().split(" "))
    lec[y][x] += 1
    lec[y][s] -= 1
    lec[t][x] -= 1
    lec[t][s] += 1
    max_x = max(max_x, s)
    max_y = max(max_y, t)

for i in range(max_y+1):
    for j in range(1, max_x+1):
        lec[i][j] += lec[i][j-1]

for i in range(1, max_y+1):
    for j in range(max_x+1):
        lec[i][j] += lec[i-1][j]

ans = 0
for i in range(max_y+1):
    for j in range(max_x+1):
        ans = max(ans, lec[i][j])

print(ans)
"""

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())

ans = N+1
t = 0; u = [0]*K; c = 0
for s in range(N):
    while t < N and c < K:
        v = A[t]
        if v <= K:
            u[v-1] += 1
            if u[v-1] == 1:
                c += 1
        t += 1
    if c == K:
        ans = min(ans, t-s)
    v = A[s]
    if v <= K:
        u[v-1] -= 1
        if u[v-1] == 0:
            c -= 1
print(ans if ans < N+1 else 0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_3_B: The Smallest Window II


class Window:
    def __init__(self, k):
        self.k = k
        self.data = [0] * k
        self.zeros = set(range(k))

    def add(self, i):
        if self.data[i-1] == 0:
            self.zeros.remove(i-1)
        self.data[i-1] += 1

    def remove(self, i):
        if self.data[i-1] == 1:
            self.zeros.add(i-1)
        self.data[i-1] -= 1

    def removable(self, i):
        return self.data[i-1] > 1

    def open(self):
        return len(self.zeros) == 0


def run():
    n, k = [int(x) for x in input().split()]
    li = [int(x) for x in input().split()]
    w = Window(k)
    i = 0
    min_ = n+1
    for j, v in enumerate(li):
        if v <= k:
            w.add(v)
            while True:
                if li[i] > k:
                    pass
                elif w.removable(li[i]):
                    w.remove(li[i])
                else:
                    break
                i += 1
            if w.open():
                if min_ > j - i + 1:
                    min_ = j - i + 1

    if min_ > n:
        print(0)
    else:
        print(min_)


if __name__ == '__main__':
    run()