# 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: -6

Explanation: 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: 1

Explanation: sub-array which has smallest

sum among all the sub-array is {1} = 1

Your Task:

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)**