LeetCode 209 - Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

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).

X. Two pointers

  int minSubArrayLen(int s, vector<int>& nums)

  {

      int n = nums.size();

      int ans = INT_MAX;

      int left = 0;

      int sum = 0;

      for (int i = 0; i < n; i++) {

          sum += nums[i];

          while (sum >= s) {

              ans = min(ans, i + 1 - left);

              sum -= nums[left++];

          }

      }

      return (ans != INT_MAX) ? ans : 0;

  }

X. Binary Search

  int minSubArrayLen(int s, vector<int>& nums)

  {

      int n = nums.size();

      if (n == 0)

          return 0;

      int ans = INT_MAX;

      vector<int> sums(n + 1, 0); //size = n+1 for easier calculations

      //sums[0]=0 : Meaning that it is the sum of first 0 elements

      //sums[1]=A[0] : Sum of first 1 elements

      //ans so on...

      for (int i = 1; i <= n; i++)

          sums[i] = sums[i - 1] + nums[i - 1];

      for (int i = 1; i <= n; i++) {

          int to_find = s + sums[i - 1];

          auto bound = lower_bound(sums.begin(), sums.end(), to_find);

          if (bound != sums.end()) {

              ans = min(ans, static_cast<int>(bound - (sums.begin() + i - 1)));

          }

      }

      return (ans != INT_MAX) ? ans : 0;

  }

Time complexity: $O(n^2)$.

  int minSubArrayLen(int s, vector<int>& nums)

  {

      int n = nums.size();

      if (n == 0)

          return 0;

      int ans = INT_MAX;

      vector<int> sums(n);

      sums[0] = nums[0];

      for (int i = 1; i < n; i++)

          sums[i] = sums[i - 1] + nums[i];

      for (int i = 0; i < n; i++) {

          for (int j = i; j < n; j++) {

              int sum = sums[j] - sums[i] + nums[i];

              if (sum >= s) {

                  ans = min(ans, (j - i + 1));

                  break; //Found the smallest subarray with sum>=s starting with index i, hence move to next index

              }

          }

      }

      return (ans != INT_MAX) ? ans : 0;

  }

Time complexity: $O(n^3)$.

  int minSubArrayLen(int s, vector<int>& nums)

  {

      int n = nums.size();

      int ans = INT_MAX;

      for (int i = 0; i < n; i++) {

          for (int j = i; j < n; j++) {

              int sum = 0;

              for (int k = i; k <= j; k++) {

                  sum += nums[k];

              }

              if (sum >= s) {

                  ans = min(ans, (j - i + 1));

                  break; //Found the smallest subarray with sum>=s starting with index i, hence move to next index

              }

          }

      }

      return (ans != INT_MAX) ? ans : 0;

  }