Solution


Approach #1 Brute force [Time Limit Exceeded]

Intuition

Do as directed in question. Find the sum for all the possible subarrays and update the as and when we get a better subarray that fulfill the requirements ().

Algorithm

  • Initialize
  • Iterate the array from left to right using :
    • Iterate from the current element to the end of vector using :
      • Find the of elements from index to
      • If sum is greater then :
        • Update
        • Start the next th iteration, since, we got the smallest subarray with starting from the current index.

Complexity Analysis

  • Time complexity: .

    • For each element of array, we find all the subarrays starting from that index which is .
    • Time complexity to find the sum of each subarray is .
    • Thus, the total time complexity :
  • Space complexity: extra space.


Approach #2 A better brute force [Accepted]

Intuition

In Approach #1, you may notice that the sum is calculated for every surarray in time. But, we could easily find the sum in O(1) time by storing the cumulative sum from the beginning(Memoization). After we have stored the cumulative sum in , we could easily find the sum of any subarray from to .

Algorithm

  • The algorithm is similar to Approach #1.
  • The only difference is in the way of finding the sum of subarrays:
    • Create a vector of size of
    • Initialize
    • Iterate over the vector:
      • Update
    • Sum of subarray from to is calculated as: , , wherein is the sum from ()th element to the th element.

Complexity analysis

  • Time complexity: .

    • Time complexity to find all the subarrays is .
    • Sum of the subarrays is calculated in time.
    • Thus, the total time complexity:
  • Space complexity: extra space.

    • Additional space for vector than in Approach #1.

Approach #3 Using Binary search [Accepted]

Intuition

We could further improve the Approach #2 using the binary search. Notice that we find the subarray with starting with an index in time. But, we could reduce the time to using binary search. Note that in Approach #2, we search for subarray starting with index , until we find that is greater than . So, instead of iterating linearly to find the sum, we could use binary search to find the index that is not lower than in the , which can be done using function in C++ STL or could be implemented manually.

Algorithm

  • Create vector of size with :

  • Iterate from to :

    • Find the value in required for minimum subarray starting from index to have sum greater than , that is:
    • Find the index in such that value at that index is not lower than the value, say
    • If we find the in , then:
      • Size of current subarray is given by:
      • Compare with the current subarray size and store minimum in

Complexity analysis

  • Time complexity: .
    • For each element in the vector, find the subarray starting from that index, and having sum greater than using binary search. Hence, the time required is for iteration over the vector and for finding the subarray for each index using binary search.
    • Therefore, total time complexity =
  • Space complexity: . Additional space for vector

Approach #4 Using 2 pointers [Accepted]

Intuition

Until now, we have kept the starting index of subarray fixed, and found the last position. Instead, we could move the starting index of the current subarray as soon as we know that no better could be done with this index as the starting index. We could keep 2 pointer,one for the start and another for the end of the current subarray, and make optimal moves so as to keep the greater than as well as maintain the lowest size possible.

Algorithm

  • Initialize pointer to 0 and to 0
  • Iterate over the :
    • Add to
    • While is greater than or equal to :
      • Update , where is the size of current subarray
      • It means that the first index can safely be incremented, since, the minimum subarray starting with this index with has been achieved
      • Subtract from and increment

Complexity analysis

  • Time complexity: . Single iteration of .
    • Each element can be visited atmost twice, once by the right pointer() and (atmost)once by the pointer.
  • Space complexity: extra space. Only constant space required for , , and .

Analysis written by @abhinavbansal0.