Leetcode # 2875. Minimum Size Subarray in Infinite Array

Problem

https://leetcode.com/contest/weekly-contest-365/problems/minimum-size-subarray-in-infinite-array/

Solution: Sliding Window

Time Complexity: O(n)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minSizeSubarray(self, nums: List[int], target: int) -> int:
    _sum = sum(nums)
    end = len(nums) * ceil(target / _sum) * 2
        
    ans = set()
    left = curr = 0
    for right in range(end):

      # do logic here to add arr[right] to curr
      curr += nums[right % len(nums)]

      while curr > target:
        # remove arr[left] from curr
        curr -= nums[left % len(nums)]
        left += 1

      # update ans
      if curr == target:
        pair = (left % len(nums), right - (left - left % len(nums)))
        if pair in ans: break
        ans.add(pair)
    
    return min((r - l + 1) for l, r in ans) if ans else -1

Last Updated on 2023/10/01 by A1go