Minimum Size Subarray Sum, DP Solution
Problem is here: https://leetcode.com/problems/minimum-size-subarray-sum/description/
Slightly different approach than the other DP solution, DP linear solution nevertheless.
Keep track of the sum of all the elements up to index i (O(n)-space and O(n)-time). With that in hands, you'll have two pointers, one for the front one of the back.
Using the sum array, you always check whether the two pointers meet the "s" criteria, if so check if the distance (front-back+1) is smaller than min, if so swap. Still in this case, you should advance the back pointer to see if the next solution meets the "s" criteria (it will be better if it does since the front-back+1 distance will be smaller). Otherwise, if it doesn't meet the "s" criteria, it is pointless to move the back pointer since it will just decrease the difference. In this case, move the front pointer.
Worst case scenario you'll move the front pointer all the way once, and the back pointer all the way once, for a total of 2n-time. Combined with the first loop to create the sum array, you'll end up with O(n)-space and O(3n)-time, still linear. Cheers, Marcelo.
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input:s = 7, nums = [2,3,1,2,4,3]Output: 2 Explanation: the subarray[4,3]has the minimal length under the problem constraint.
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).
Slightly different approach than the other DP solution, DP linear solution nevertheless.
Keep track of the sum of all the elements up to index i (O(n)-space and O(n)-time). With that in hands, you'll have two pointers, one for the front one of the back.
Using the sum array, you always check whether the two pointers meet the "s" criteria, if so check if the distance (front-back+1) is smaller than min, if so swap. Still in this case, you should advance the back pointer to see if the next solution meets the "s" criteria (it will be better if it does since the front-back+1 distance will be smaller). Otherwise, if it doesn't meet the "s" criteria, it is pointless to move the back pointer since it will just decrease the difference. In this case, move the front pointer.
Worst case scenario you'll move the front pointer all the way once, and the back pointer all the way once, for a total of 2n-time. Combined with the first loop to create the sum array, you'll end up with O(n)-space and O(3n)-time, still linear. Cheers, Marcelo.
public class Solution
{
public int MinSubArrayLen(int s, int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
int[] sum = new int[nums.Length];
//Base
sum[0] = nums[0];
for (int i = 1; i < sum.Length; i++)
sum[i] = nums[i] + sum[i - 1];
//"Construction"
int min = Int32.MaxValue;
int front = 0;
int back = 0;
while (back < nums.Length && front < nums.Length)
{
if (sum[front] - sum[back] + nums[back] < s)
{
front++;
}
else
{
min = Math.Min(min, front - back + 1);
back++;
}
}
return (min == Int32.MaxValue) ? 0 : min;
}
}
Hm, interesting, I've never thought about this problem from DP perspective... I looked at it as a variation of a sliding window in which we try to extend the window until the condition is met and then advance its beginning. Using this idea requires O(N) time and O(1) space:
ReplyDeleteclass Solution {
public:
int minSubArrayLen(int s, const vector& nums) {
if (nums.empty()) return 0;
int left = 0;
int right = 1;
int sum = nums.front();
int min_so_far = numeric_limits::max();
while (left < nums.size() && right < nums.size()) {
while (sum < s && right < nums.size()) sum += nums[right++];
while (sum >= s && left < nums.size()) {
min_so_far = min(min_so_far, right - left);
sum -= nums[left++];
}
}
return min_so_far != numeric_limits::max() ? min_so_far : 0;
}
};
Cheers,
Taras