Smallest Subarray Sum at Least S
Python
Hard
2 views
Problem Description
Read n integers (can be positive, zero) and target S. Compute the minimum length of a contiguous subarray with sum >= S. If not found, output 0.
Input Format
First line n S. Second line n integers (all non-negative).
Output Format
One integer minLen or 0.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0]); S=int(p[1])
a=list(map(int,p[2:2+n]))
left=0
sm=0
best=n+1
for right in range(n):
sm+=a[right]
while left<=right and sm>=S:
ln=right-left+1
if ln<best:
best=ln
sm-=a[left]
left+=1
sys.stdout.write('0' if best==n+1 else str(best))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!