'''
keys: 
Solutions:
Similar: 862
T:
S:
'''
from typing import List


class Solution:
    
    # two pointers; T: O(n), S: O(1)
    def minSubArrayLen1(self, s: int, nums: List[int]) -> int:
        left = 0; sum_ = 0; res = float("inf")
        for right, num in enumerate(nums):
            sum_ += num
            while sum_ >= s: # use while to update the anchor
                res = min(res, right - left + 1)
                sum_ -= nums[left] # minus the leftmost one
                left += 1 # move left one step to the right
        return res if res != float("inf") else 0
    
    
    # binary search. T: O(nlogn), S: O(1); or O(n) if sums created
    def minSubArrayLen2(self, s: int, nums: List[int]) -> int:
        res = float("inf")
        for idx, n in enumerate(nums[1:], 1):
            nums[idx] = nums[idx - 1] + n # turning nums into prefix sums
        left = 0
        for right, pre_sum in enumerate(nums): # prefix_sum
            if pre_sum >= s:
                left = self.find_left(left, right, nums, s, pre_sum)
                res = min(res, right - left + 1)
        return res if res != float("inf") else 0
    
    def find_left(self, left, right, nums, s, pre_sum):
        while left < right:
            mid = left + (right - left) // 2
            if pre_sum - nums[mid] >= s: # nums[mid] is prefix_sum of 0:mid
                left = mid + 1
            else:
                right = mid
        return left
        
    
    # brute-force, T: O(n^2); S: O(1) 
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        res = float("inf")
        for i in range(len(nums)):
            sum_ = 0
            for j in range(i, len(nums)):
                sum_ += nums[j]
                if sum_ >= s:
                    res = min(res, j-i+1)
                    break # find a subarray for 2nd loop, break the 2nd loop
        return res if res != float("inf") else 0