Kadane’s Algorithm: minimum size subarray sum

Coding Interview Questions

1 min read

Problem Statement:

You are given an array.

You need to find the subarray which has the smallest possible sum.

Example:

Input: arr[] = {1, -2, 3, 4}


Output: -2

Explanation: {-2} = -2

Solution Explanation:

In the solution we will iterate through each element, then we will check the current sum with the minimum result sum.

If the new sum is smaller than the minimum sum, then we update the sum.

If the current sum is greater than 0, then we reset the current sum to zero.

Time Complexity: O(n)

Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;


int solution(vector<int> arr) 
{
    int minSum = INT_MAX;
    int curSum = 0;

    for(int i = 0; i < arr.size(); i++) 
    {
        if (curSum > 0)
            curSum = arr[i];

        else
            curSum += arr[i];

        minSum = min(minSum, curSum);;
    }
    return minSum;
}



int main()
{
    vector<int> arr =  {1, 2, 3, -4, 5};
  
    cout << solution(arr);
    return 0;
}