[백준] 15565번: 귀여운 라이언

https://www.acmicpc.net/problem/15565

initial

We want to find the shortest subsequence with k or more value 1 in that subsequence. It is thus a two poitner where once we find a valid subsequence, we shift the left pointer to the next value 1.

my initial wrong code: not sure what i did here but I didnt shift left pointer to next 1 but just until we have an invalid sequence of less than k 1s.

n,k = map(int,input().split())
lst = list(map(int,input().split()))
dic={1:0, 2:0}

count =int(10e9)
left,right = 0,0
while True:
    if right==n:
        break
    dic[lst[right]]+=1
    right+=1
    if dic[1]>=k:
        count = min(count, right-left-1)
        while dic[1]>=k:
            if left==n:
                break
            dic[lst[left]]-=1
            left+=1
print(count)

solution

my corrected code after debugging.

Notice I put the magic elif right==n trick after the 'if dic[1]>=k' and before we access the lst[right] in the next statements to prevent list index out of range error. If I placed that magic before "if dic[1]>=k", then the loop prematurely ends without considering the last rightmost element in the list.

n,k = map(int,input().split())
lst = list(map(int,input().split()))
dic={1:0, 2:0}

count =int(10e9)
left,right = 0,0
while True:
    if dic[1]>=k:
        count = min(count, right-left)
        while left<n:
            dic[lst[left]]-=1
            left+=1
            if lst[left]==1:
                break
    elif right==n:
        break
    else:
        dic[lst[right]]+=1
        right+=1
if count == int(10e9):
    print(-1)
else:
    print(count)

other solutions:
i googled but some used while left and right pointer < n so even if right pointer reaches n, we shift left pointer. I haven't found one that is like mine.

complexity

The provided code appears to find the shortest subarray within a given list lst such that the number of occurrences of the value 1 in the subarray is at least k. Here's the complexity analysis of the code:

1. Input Reading (Linear Time):

   • Reading n and k takes constant time.
   • Reading the list lst with n elements using list(map(int, input().split())) takes linear time, O(n), as it processes each element in the list.

2. Initialization (Constant Time):

   • Creating the dictionary dic with keys 1 and 2 and initializing their values to 0 takes constant time.

3. Sliding Window (Linear Time):

   • The code uses a sliding window approach to find the shortest subarray with at least k occurrences of 1.
   • The while loop runs until it either breaks (when it reaches the end of the list) or the condition dic[1] >= k is met.
   • The loop keeps track of the current window using left and right pointers and updates the dic dictionary to count the occurrences of 1 and 2 in the window.
   • When dic[1] >= k, it calculates the length of the subarray (right - left) and updates the count variable with the minimum length encountered so far.
   • When right reaches the end of the list, the loop terminates.
   • All operations within the loop (updating dic, left, and right, and calculating lengths) are constant time.

4. Printing (Constant Time):

   • The code prints either the minimum subarray length (count) or -1 if no such subarray is found. Printing takes constant time.

Overall, the time complexity of the code is determined by the sliding window part, which iterates through the list once. Therefore, the time complexity is O(n).

The space complexity is O(1) because the size of the dic dictionary and other variables remains constant regardless of the input size.