Home Discussions Write at Opengenus IQ
×

Search anything:

Smallest sum contiguous subarray

Binary Tree book by OpenGenus

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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

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

Algorithm 3 (Efficient Approach)

Surprisingly, it is possible to solve the problem in O(N) time, using 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:
  1. The subarray only contains the element array[k].
  2. 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 Xk. From the above propositions, we get the relation: Xk = min(array[k], array[k] + Xk-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 O(N) and it is the 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)
where N is the number of elements

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)
where N is the number of elements

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

—
Smallest sum contiguous subarray
Share this