Table of Contents
Leetcode 209. Minimum Size Subarray Sum
Problem
Given an array of positive integers nums
and a positive integer target
, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr]
of which the sum is greater than or equal to target
. If there is no such subarray, return 0
instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4] Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0
Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
Follow up: If you have figured out the O(n)
solution, try coding another solution of which the time complexity is O(n log(n))
.
Source : Leetcode 209. Minimum Size Subarray Sum
Solution Approach – 1: Two Pointers
We can use two pointer approach to solve this problem. Please do not get confused with pointers of C or C++ or any other languages. Here, by pointer we simply mean index of the array.
Two pointer (or index) i and j will initially point to the first index of the given array. Then j will move forward and we will keep track of the summation of elements j passes. When summation will be >= target, we will move i forward until summation becomes < target. During this process of i’s movement, we will keep track of the length between i and j and save the minimum length.
C++ Code
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len = nums.size(); if(len == 0) return 0; int i = 0; int j = 0; int sum_so_far = 0; int min_subarray_length = INT_MAX; // variable j will move forward and update sum_so_far // variable i will wait at his position while(j < len){ sum_so_far += nums[j]; /* when sum_so_far is >= target, that length is a possible answer. We will update our answer with that. But, may be, if we eleminate zero or more element from the position of i, sum_so_far might not be reduced that much to become < target. So, we will try to eliminate elements from the position of i and check if sum_so_far is still >= target or not. */ while(sum_so_far >= target && i <= j){ min_subarray_length = min(min_subarray_length, j - i + 1); sum_so_far -= nums[i]; //eliminate the i-th element i++; // and move i forward towards j } j++; } if(i == 0) // that measn, we never found sum_so_far to be >= target return 0; //hence, there is no contiguous subarray and min_subarray_length = 0 return min_subarray_length; } };
Conclusion
This is a medium level leetcode problem that can be solved using both two pointer and binary search approach. If you like the way we explained it, please write a comment. If you hate it, write comment as well. 🙂 There are other posts you may like listed below.
Happy Coding! 🙂
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
To the foolishhungry.com administrator, Thanks for the well-structured and well-presented post!
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you. 20bet
To the foolishhungry.com admin, Nice post!
To the foolishhungry.com admin, Your posts are always well-formatted and easy to read.
Hi foolishhungry.com owner, Your posts are always well organized and easy to understand.
Hello foolishhungry.com webmaster, Thanks for the well-presented post!
Dear foolishhungry.com administrator, Thanks for the informative and well-written post!
Hi foolishhungry.com owner, Your posts are always a great read.
Hi foolishhungry.com administrator, Thanks for the well-researched and well-written post!
Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi
Dear foolishhungry.com webmaster, Thanks for the well-structured and well-presented post!
Hi foolishhungry.com owner, Thanks for the post!
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.info/en/join?ref=UM6SMJM3
Hello foolishhungry.com admin, Thanks for the well-structured and well-presented post!
To the foolishhungry.com owner, Your posts are always informative.
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.com/en/join?ref=V3MG69RO
To the foolishhungry.com admin, Your posts are always well-structured and logical.
To the foolishhungry.com owner, Your posts are always well-written and easy to understand.
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
Your point of view caught my eye and was very interesting. Thanks. I have a question for you.
Hi foolishhungry.com owner, Your posts are always well researched and well written.
Hi foolishhungry.com administrator, Your posts are always well presented.
Dear foolishhungry.com administrator, Good to see your posts!
Hello foolishhungry.com administrator, You always provide great information and insights.
To the foolishhungry.com owner, Your posts are always well received by the community.
Hi foolishhungry.com administrator, Your posts are always well presented.
To the foolishhungry.com webmaster, You always provide clear explanations and step-by-step instructions.
Hi foolishhungry.com admin, Your posts are always well-written and easy to understand.
Dear foolishhungry.com owner, You always provide helpful information.