Find the subarray with sum to a Given Value.

Objective: Given an array (non-negative) and an integer, Find the Subarray whose sum is equal to the given integer.

Examples:

int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 };
Integer = 55
Output : 55 is found between indexes 2 and 4
And Elements are : 14 22 19

Approach :

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

  • Idea is to keep adding all the elements to the currSum
  • Keep checking if the currSum<Sum
  • If currSum gets greater than the Sum then start reducing the currSum from the beginning of the array using “start”if any time currSum=Sum, Stop and return

Complete Code:


Output:

55 is found between indexes 2 and 4
And Elements are :  14 22 19

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

9 Responses

  1. Deep Shah says:

    I think it can be done in O(n) time using Kadane’s Algorithm (http://en.wikipedia.org/wiki/Maximum_subarray_problem)

    • tutorialhorizon says:

      Yes it can be, but the solution provided is also O(n).

      • Deep Shah says:

        tutorialhorizon Thanks for the reply.

        This is the other solution which I thought of . It uses only one for loop. and no nested loops inside.

        // Kadanes Algorithm

        private static int maxSubarray(int[] arr) {

        // TODO Auto-generated method stub

        int max_sum = 0;

        int sum = 0;

        int startIndex = 0; // intially start index is at 0

        int endIndex = 0; // intially end index is at 0 position

        int tempStart = 0; // intially start = tempstart = 0

        if(arr.length == 0){

        System.out.println(“No Elements in Array”);

        return -1;

        }

        else if(arr.length == 1){

        System.out.println(“Array contains only single element”);

        startIndex = 0;

        endIndex = 0;

        System.out.println(“Start Index : “+startIndex + “t End Index :”+endIndex);

        return arr[0];

        }

        for(int i = 0; i<arr.length;i++){

        sum = sum + arr[i];

        if(max_sum < sum){

        max_sum = sum;

        startIndex = tempStart; // max_sum < sum so we found a greater sum from last tempstart to current element

        endIndex = i; // make end as current element

        }

        else if(sum < 0){

        sum = 0;

        tempStart = i + 1; // if sum is less than 0, make a fresh start with right element

        }

        }

        System.out.println("Start Index : "+startIndex + "t End Index :"+endIndex);

        System.out.print("Largest Sum is obtained from : ");

        for(int i = startIndex; i<= endIndex;i++){

        System.out.print(arr[i]+", ");

        }

        return max_sum;

        }

        • Holden says:

          Have you solved this problem with Kandane’s algorithm? Could you please write your code in Ideone and share its link here?
          Since it is not readable here.

  2. Holden says:

    Thank you for the great post.

    Don’t you think this ‘for’:

    for (int i = 0; i <= arrA.length; i++) {

    should be:

    for (int i = 0; i < arrA.length; i++) {

    ?

  3. Holden says:

    There is a while in ‘for’ loop, is it still O(n) solution? Your proposed logic seems linear; But in textbooks, we read if there is two nested loop, time complexity will be quadratic.

    • Holden says:

      I think I got it! These 2 loops are independent! If two loops are not independent, time complexity will be O(n^2). Thank you

      • tutorialhorizon says:

        Yes holden you got it right. Though there are two nested loops but still every element will be traversed only once.

  4. jafar basha says:

    In an Array, find the Smallest Contiguous Subarray with Sum to a Given Value.
    https://github.com/jafar9/c-prg/blob/master/smallestsubarray.c

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: