Johnnn

Let's go

Find subarray with a given sum, algorithm and time complexity with example in C,C++,Python and java

by · Published · Updated


In programming, it is common to encounter scenarios where we need to find a subarray within a larger array that has a specific sum. This task can be solved efficiently using a variety of algorithms. In this blog post, we will explore a popular approach to solve the problem and provide code examples in four widely used programming languages: C, C++, Python, and Java.

Algorithm:
The algorithm we will discuss is based on the sliding window technique. It involves using two pointers, one marking the start of the subarray and the other marking the end. The window starts from the leftmost element and expands towards the right until the desired sum is reached or exceeded. If the sum becomes greater than the desired sum, the window contracts from the left by incrementing the left pointer. This process continues until we find a subarray with the given sum or until the end of the array is reached.

Time Complexity:
The time complexity of this algorithm is O(n), where n is the size of the array. The algorithm performs a single pass through the array, and each element is visited at most twice (once by the left pointer and once by the right pointer). Thus, the time complexity is linear.

Code Examples:

  1. C:
#include<stdio.h>

void findSubarrayWithGivenSum(int arr[], int n, int sum) {
    int start = 0, end = 0, currSum = arr[0];

    while (end < n) {
        if (currSum == sum) {
            printf("Subarray found from index %d to %dn", start, end);
            return;
        }
        if (currSum < sum) {
            end++;
            currSum += arr[end];
        }
        else {
            currSum -= arr[start];
            start++;
        }
    }

    printf("No subarray found with the given sumn");
}

int main() {
    int arr[] = {1, 4, 20, 3, 10, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 33;

    findSubarrayWithGivenSum(arr, n, sum);

    return 0;
}
  1. C++:
#include <iostream>
#include <vector>

using namespace std;

void findSubarrayWithGivenSum(vector<int>& arr, int sum) {
    int start = 0, end = 0, currSum = arr[0];

    while (end < arr.size()) {
        if (currSum == sum) {
            cout << "Subarray found from index " << start << " to " << end << endl;
            return;
        }
        if (currSum < sum) {
            end++;
            currSum += arr[end];
        }
        else {
            currSum -= arr[start];
            start++;
        }
    }

    cout << "No subarray found with the given sum" << endl;
}

int main() {
    vector<int> arr = {1, 4, 20, 3, 10, 5};
    int sum = 33;

    findSubarrayWithGivenSum(arr, sum);

    return 0;
}
  1. Python:
def find_subarray_with_given_sum(arr, target_sum):
    start = 0
    end = 0
    curr_sum = arr[0]

    while end < len(arr):
        if curr_sum == target_sum:
            print("Subarray found from index", start, "to", end)
            return
        if curr_sum < target_sum:
            end += 1
            curr_sum += arr[end]
        else:
            curr_sum -= arr[start]
            start += 1

    print("No subarray found with the given sum")


arr = [1, 4, 20, 3, 10, 5]
target_sum = 33

find_subarray_with_given_sum(arr, target_sum)
  1. Java:
class Main {
    static void findSubarrayWithGivenSum(int[] arr, int sum) {
        int start = 0, end = 0, currSum = arr[0];

        while (end < arr.length) {
            if (currSum == sum) {
                System.out.println("Subarray found from index " + start + " to " + end);
                return;
            }
            if (currSum < sum) {
                end++;
                currSum += arr[end];
            } else {
                currSum -= arr[start];
                start++;
            }
        }

        System.out.println("No subarray found with the given sum");
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 20, 3, 10, 5};
        int sum = 33;

        findSubarrayWithGivenSum(arr, sum);
    }
}

Conclusion:
In this blog post, we explored an efficient algorithm for finding a subarray with a given sum using the sliding window technique. We discussed the algorithm’s time complexity, which is linear, and provided code examples in four popular programming languages: C, C++, Python, and Java. Next time you encounter a problem requiring finding a subarray with a specific sum, you can utilize this algorithm as a starting point for your solution. Happy coding!

You may also like...