1004. Max Consecutive Ones III (Array, Binary Search, Sliding Window, Prefix Sum)

링크 - https://leetcode.com/problems/max-consecutive-ones-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 sliding window문제이다. right를 for문으로 돌리면서 k보다 높은 개수의 0을 1로 만들었을 때, left를 옮기는 식으로 풀면된다.

Code

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        ans = 0

        left = 0
        used_k = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                used_k += 1

            while used_k > k:
                if nums[left] == 0:
                    used_k -= 1
                left += 1

            ans = max(ans, right - left + 1)

        return ans

Complexity

Time Complexity: O(n) nums를 한번 linear하게 탐색하므로 평균적으로 O(n)이다. 최악의 경우는 right와 left가 매번 한번씩 움직이는 경우이다. (2n)

Space Complexity: O(1)