# Cracking the coding interview: Smallest sum contiguous subarray — 10

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.

Example 1:

`Input: arr[] = {3,-4, 2,-3,-1, 7,-5}Output: -6Explanation: sub-array which has smallest sum among all the sub-array is {-4,2,-3,-1} = -6`

Example 2:

`Input:arr[] = {2, 6, 8, 1, 4}Output: 1Explanation: sub-array which has smallestsum among all the sub-array is {1} = 1`

You don’t need to read input or print anything. The task is to complete the function smallestSubarraySum() which takes arr[] and N as input parameters and returns the sum of subarray with minimum sum.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 106
-107 ≤ A[i] ≤ 107

Solution:
In this question, Kadane’s algorithm is an ideal solution for searching for the maximum sum of a contiguous subarray in an array. How it works is to calculate the maximum subarray pausing at the previous position, but simply breaking down it into a smaller issue. Similarly, it could be considered as a technique of dynamic programming.

Time complexity: O(N)
Space complexity: O(1)

--

--

👨‍💻