Minimum Size Subarray Sum, DP Solution

-
Problem is here: https://leetcode.com/problems/minimum-size-subarray-sum/description/

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, Boris.


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;
 }
}

Comments

  1. TarasDecember 22, 2018 at 9:18 PM

    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:

    class 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

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more