DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Smallest sum contiguous subarray

Problem statement

Given an array arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the minimum sum and return its sum.

link to the problem could be found here, https://practice.geeksforgeeks.org/problems/smallest-sum-contiguous-subarray/1

Sample Input and Outputs

Example 1

Input: 
    arr[] = {3,-4, 2,-3,-1, 7,-5}
Output: -6

Explanation: 
sub-array which has smallest 
sum among all the sub-array is {-4,2,-3,-1} = -6
Enter fullscreen mode Exit fullscreen mode

Example 2

Input:
    arr[] = {2, 6, 8, 1, 4}
Output: 1
Explanation: 
sub-array which has smallest
sum among all the sub-array is {1} = 1
Enter fullscreen mode Exit fullscreen mode

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Solution

Here the most simplest and efficient solution is based upon the Kadane’s Algorithm. Which sweeps the iterator (here mentioned as current sum) from element to element, meanwhile after every updated value of the iterator, or current sum, this value is being checked with minimum result sum, if minimum sum get a further minimum value, then the contents are updated, else not.

Meanwhile if the current sum any where exceeds the 0, then we need to reset the current sum to zero. This means for any value here on it would make sense to ignore the subarray till this point, as if considered would result into few positive numbers, that inturn would oppose the interest of the problem to find minimum number (to which only negative numbers contribute). So avoid taking positive numbers into current sum.

class Solution
{
    static int smallestSumSubarray(int a[], int size) {
        int minSum = Integer.MAX_VALUE;
        int curSum = 0;
        for(int i : a) {
            curSum += i;
            minSum = Math.min(minSum, curSum);
            curSum = Math.min(curSum, 0);
        }
        return minSum;
    }
}
Enter fullscreen mode Exit fullscreen mode

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay