Grokking the Coding Interview: Patterns for Coding Questions
0% completed
Smallest Subarray With a Greater Sum (easy)
Problem Statement
Given an array of positive integers and a number ‘S,’ find the length of the smallest contiguous subarray whose sum is greater than or equal to 'S'. Return 0 if no such subarray exists.
Example 1:
Input: arr = [2, 1, 5, 2, 3, 2], S=7
Output: 2
Explanation: The smallest subarray with a sum greater than or equal to '7' is [5, 2].
Example 2:
Input: arr = [2, 1, 5, 2, 8], S=7
Output: 1
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].
Example 3:
Input: arr = [3, 4, 1, 1, 6], S=8
Output: 3
.....
.....
.....
Like the course? Get enrolled and start learning!
S
Salah Osman
· 3 years ago
Why would time complexity be O(n+n) instead of maybe something like O(n*n). [1,2,3...infinity], s = infinity. While loop would have to run in the worst case infinity times with each process?
Show 1 reply