Problem

Submissions

Hints & solutions

Discuss

Minimum Sum Subarray

Easy

0/40

Average time to solve is 15m

Contributed by

12 upvotes

Asked in companies

Problem statement

You have been given an array/list 'ARR' consisting of 'N' integers.

Your task is to find the minimum possible sum of a non-empty subarray of this array.

Note:

An array 'C' is a subarray of array 'D' if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array 'D'. For example, all the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

For Example :

Input: 'N' = 3 , 'ARR' =  [-5, 10 , 0]
Output: -5

Explanation : The non empty subarrays possible for 'ARR' are [-5], [10], [0], [-5, 10], [-5, 0], [10, 0], [-5, 10, 0]. The sum of the elements of these subarrays are -5, 10, 0, 5, -5, 10, 5. The minimum of them is -5.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list.

Output Format :

For each test case, return the minimum possible sum of any subarray of the array/list.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
-10^5 <= ARR[i] <=10^5

Time Limit : 1 second

Sample Input 1 :

1
3 
2 -7 -11

Sample Output 1:

-18

Explanation for Sample 1:

The non empty subarrays possible for the given array are [2], [-7], [-11], [2, -7], [2, -11], [-7, -11], [2, -7, -11]. The sum of the elements of these subarrays are 2, -7, -11, -5, -9, -18, -16. The minimum of them is -18.

Sample Input 2 :

2
4
-1 -2 -5 -3
4
1 2 5 3

Sample Output 2 :

-11
1

Hint 1

Hint 2

Hint 3

Naively iterate over all possible subarrays.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive Approach

We will iterate through all possible boundaries of the subarrays in the given array with the help of two nested loops.

Then, we will iterate through each subarray with the help of another loop and find the sum of that subarray. We will maintain the minimum subarray sum through our iterations and finally return it.

Time Complexity

O(N ^ 3), where ‘N’ denotes the number of elements in an array.

There are N * (N + 1) / 2 subarrays in total, and we are iterating over every subarray in linear time, so the overall time complexity will be O(N ^ 3).

Space Complexity

O(1), i.e. constant space complexity.

As we are not storing anything.

(100% EXP penalty)

Minimum Sum Subarray

Console