Start learning free

LESSON 311 OF 410 · SLIDING WINDOW

Subarray of Given Sum II in O(n) Time Complexity using Java

Practice O(n) Read the full explanation

Given an array of non-negative integers and a number target, find a continuous subarray whose sum is equal to target.

Return the start and end indices denoting this subarray, or -1 and -1 if there is none.

If there are multiple solutions, you can return any of them.


Example:

Input: nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], target = 21
Output: [2, 6]
Explanation: 5 + 2 + 1 + 3 + 10 = 21

Note:

1. The input array contains only non-negative integers.

2. Your algorithm should run in O(n) time and use O(1) extra space.


STEP 1 OF 8
    Ctrl + Enter to check

    JAVA · SLIDING WINDOW

    Subarray Of Given Sum Ii in Java, explained

    Understanding the Problem

    The core challenge of this problem is to find a continuous subarray within a given array of non-negative integers that sums up to a specified target value. This problem is significant in various applications such as financial analysis, where one might need to find a period with a specific sum of transactions.

    Potential pitfalls include misunderstanding the requirement for a continuous subarray and not optimizing the solution to meet the O(n) time complexity constraint.

    Approach

    To solve this problem, we can use the sliding window technique, which is efficient for problems involving subarrays or substrings. The idea is to maintain a window that expands and contracts to find the target sum.

    Here’s a step-by-step approach:

    1. Initialize two pointers, start and end, both set to the beginning of the array.
    2. Maintain a variable currentSum to store the sum of the current window.
    3. Expand the window by moving the end pointer and adding the value at end to currentSum.
    4. If currentSum exceeds the target, contract the window by moving the start pointer and subtracting the value at start from currentSum.
    5. Continue this process until you find a window where currentSum equals the target.

    Algorithm

    Here is a detailed breakdown of the algorithm:

    1. Initialize start to 0 and currentSum to 0.
    2. Iterate through the array with end from 0 to the length of the array.
    3. Add the value at end to currentSum.
    4. While currentSum is greater than the target, subtract the value at start from currentSum and increment start.
    5. If currentSum equals the target, return the indices [start, end].

    Code Implementation

    public class SubarraySum {
    public static int[] findSubarrayWithGivenSum(int[] nums, int target) {
        int start = 0;
        int currentSum = 0;

        for (int end = 0; end < nums.length; end++) {
            // Add the current element to the currentSum
            currentSum += nums[end];

            // While currentSum is greater than target, subtract the element at start
            while (currentSum > target) {
                currentSum -= nums[start];
                start++;
            }

            // Check if we have found the target sum
            if (currentSum == target) {
                return new int[]{start, end};
            }
        }

        // If no subarray is found, return an empty array
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 5, 2, 1, 3, 10, 2, 1};
        int target = 21;
        int[] result = findSubarrayWithGivenSum(nums, target);
        if (result.length == 2) {
            System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
        } else {
            System.out.println("No subarray found with the given sum.");
        }
    }
}

    Complexity Analysis

    The time complexity of this approach is O(n) because each element is processed at most twice, once by the end pointer and once by the start pointer. The space complexity is O(1) as we are using only a few extra variables.

    Edge Cases

    Consider the following edge cases:

    • An empty array: The function should return an empty array.
    • An array where no subarray sums to the target: The function should return an empty array.
    • An array where the entire array sums to the target: The function should return the indices of the entire array.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small arrays.
    • Cases where the subarray is at the beginning, middle, and end of the array.
    • Edge cases such as an empty array or an array with no valid subarray.

    Thinking and Problem-Solving Tips

    When approaching such problems, it is crucial to:

    • Understand the problem requirements and constraints thoroughly.
    • Think about different approaches and their trade-offs.
    • Start with a simple solution and then optimize it.
    • Practice similar problems to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find a continuous subarray with a given sum in an array of non-negative integers. We explored the sliding window technique, provided a detailed algorithm, and implemented the solution in Java. Understanding and solving such problems is essential for improving algorithmic thinking and coding skills.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free