Get this book -> Problems on Array: For Interviews and Competitive Programming

You are given an array of n integers. The task is to find the sum of the subarray which has the smallest possible sum.

**Note: Subarray is an array formed by a block of contiguous elements of the parent ( or original ) array.**

## Examples

```
Input:
No. of elements in the array = 5
Array : -4 3 -1 -6 8
Output:
-8
```

**Explanation: The subarray [-4, 3, -1, -6] gives the minimum sum.**

```
Input:
No. of elements in the array = 5
Array : 3 5 1 2 4
Output:
1
```

**Explanation: The subarray [1] gives the minimum sum.**

# Approach

## Algorithm 1 (Brute-force)

We simply iterate over all the possible subarrays, find the sum of elements in each subarray and find the minimum of them.### Pseudocode

```
// Using 1-indexing
//array[i] represents the ith element in the input array
ans = INFINITY
for i in 1 to size_of_array:
for j in i to size_of_array:
sum = 0
for k in i to j:
sum += array[k]
ans = min(ans,sum)
```

print(ans)

The time complexity of this algorithm is **.**

*O(N*^{3})## Algorithm 2 (Optimized Brute-force)

For this we remove one loop from Algorithm 1 to increase efficiency. We can calculate the sum at the same time when the end of the subarray moves.### Pseudocode

```
// Using 1-indexing
//array[i] represents the ith element in the input array
ans = INFINITY
for i in 1 to size_of_array:
sum = 0
for j in i to size_of_array:
sum += array[j]
ans = min(ans,sum)
```

print(ans)

The time complexity of this algorithm is **.**

*O(N*^{2})## Algorithm 3 (Efficient Approach)

Surprisingly, it is possible to solve the problem in**time, using**

*O(N)***dynamic programming**. The idea is to calculate, for each index :

**the minimum sum of a subarray that ends at that index.**And then the answer will be the minimum of all these sums.

Thus the problem reduces to the subproblem:

**find the minimum sum of a subarray that ends at the index k.**Thus, there are only two possibilities:

- The subarray only contains the element array[k].
- The subarray consists of a subarray that ends at position k-1, followed by the element at position k.

Let us denote the the minimum sum of a subarray that ends at the index k by X_{k}. From the above propositions, we get the relation: **X _{k} = min(array[k], array[k] + X_{k-1} )**

### Pseudocode

`// Using 1-indexing`

//array[i] represents the ith element in the input array

ans = INFINITY

sum = 0

for i in 1 to size_of_array:

sum = min(array[i], array[i] + sum)

ans = min(ans, sum)

print(ans)

The time complexity of this algorithm is

**and it is the**

*O(N)***best possible time complexity**as we need to go through all the array elements at least once.

### C++ Code

### C++

```
//C++ program to find smallest sum subarray
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
```

//function declaration
int smallestSubarraySum(int a[], int n){

int sum = 0;
int ans = INT_MAX;
for(int i = 0 ; i < n ; ++i){
sum = min(a[i], a[i] + sum);
ans = min(ans, sum);
}

return ans;
}

int main(){
//input
int n;
cout << "No. of elements in the array = ";
cin >> n;
int a[n];
cout << "Array : ";
for(int i = 0 ; i < n ; ++i){
cin >> a[i];
}

//output
cout << smallestSubarraySum(a,n);
return 0;
}

### Time Complexity

- Worst case time complexity:
`O(N)`

- Average case time complexity:
`Ξ(N)`

- Best case time complexity:
`Ξ©(N)`

- Auxiliary space:
`O(1)`

- Space complexity:
`Θ(N)`

**TRY IT YOURSELF** : Modify the above code to reduce its space complexity to *O(1).*

## An Interesting Problem

Solve the**smallest sum subarray**problem using Kadane's algorithm.

## Solution

**Kadane's algorithm**gives the answer of

**maximum sum subarray problem**( i.e. sum of the subarray with the maximum sum ). If we replace each array[i] with -array[i] then we apply Kadane's algorithm let's name the output X. Then

**negative of X**will give us the answer of smallest sum subarray problem.

#### Pseudocode

```
// Using 1-indexing
//array[i] represents the ith element in the input array
```

for i in 1 to n:
array[i] = -1*array[i]

//Kadane's algorithm
ans = -INFINITY
sum = 0
for i in 1 to size_of_array:
sum = max(array[i], array[i] + sum)
ans = max(ans, sum)

print(-1*ans)

The time complexity of this algorithm is

*O(N)**(same as Kadane's Algorithm)*.

### C++ Code

### C++

```
//C++ program to find smallest sum subarray
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
```

int kadane(int a[], int n){
int ans = INT_MIN;
int sum = 0;

for(int i = 0 ; i < n ; ++i){
sum = max(a[i], a[i] + sum);
ans = max(ans, sum);
}

return ans;
}

int smallestSubarraySum(int a[], int n){
for(int i = 0 ; i < n ; ++i){
a[i] = -1*a[i];
}

return -1*kadane(a,n);
}

int main(){
//input
int n;
cout << "No. of elements in the array = ";
cin >> n;
int a[n];
cout << "Array : ";
for(int i = 0 ; i < n ; ++i){
cin >> a[i];
}

//output
cout << smallestSubarraySum(a,n);
return 0;
}

### Time Complexity

- Worst case time complexity:
`O(N)`

- Average case time complexity:
`Ξ(N)`

- Best case time complexity:
`Ξ©(N)`

- Auxiliary space:
`O(1)`

- Space complexity:
`Θ(N)`

**Feel free to share your approach in the discussion thread below. Happy Coding :)**