Array - 28: Find smallest sub-array length with given Sum

Показать описание

Solution - 1: When you've all positive numbers
- We take two variable start & end which're pointing to starting element
- We take another variable window_sum = 0 & smallestSubArrayLength
- Now start from 1st element & add into window_sum
- If window_sum == given_sum, then we've got our subarray, at this moment you check of end - start + 1 is less than smallestSubArrayLength, then you update the smallestSubArrayLength wih end - start + 1
- If window_sum is less than given-sum then keep on adding element
- If window_sum is greater than given-sum then we decrease the element from the starting
- At last you return smallestSubArrayLength

Time Complexity: O(n)
Space Complexity: O(1)

Solution - 2: For any case
- We take variable 'end' which're pointing to starting element & smallestSubArrayLength
- We take another variable total_sum_till_here = 0 & a map where key'll store total_sum_till_here & value will be index where this sum is present
- Now start from 1st element & if total_sum_till_here == given-sum, you've got sub-array, you check if end - index of that value is less than smallestSubArrayLength, then you update the value of smallestSubArrayLength
- If total_sum_till_here - given_sum is present in map, it means value exists, so subarray will from start+1 to end
- If total_sum_till_here - given_sum is not present, then you total_sum_till_here as map key
- At last, you update smallestSubArrayLength

Time Complexity: O(n)
Space Complexity: O(n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★