Algocademy Logo

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


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

Return the start and end indices denoting this subarray.

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


Example:

Input: nums = [1, 1, 5, 2, 1, 3, 10, 2, 1], k = 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.


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, or in signal processing, where a specific pattern needs to be identified within a signal.

Potential pitfalls include misunderstanding the requirement for the subarray to be continuous and not considering the constraints of non-negative integers, which simplifies the problem by ensuring that the sum of any subarray will always increase or stay the same as we add more elements.

Approach

To solve this problem, we can use a sliding window approach, which is optimal for problems involving subarrays or substrings. The sliding window technique involves maintaining a window that expands and contracts to find the desired subarray.

Here’s a step-by-step approach:

  1. Initialize two pointers, start and end, both set to the beginning of the array.
  2. Initialize a variable current_sum to keep track of the sum of the current window.
  3. Expand the window by moving the end pointer and adding the value at end to current_sum.
  4. If current_sum exceeds the target, contract the window by moving the start pointer and subtracting the value at start from current_sum.
  5. Continue this process until current_sum equals the target or the end pointer reaches the end of the array.

Algorithm

Here is a step-by-step breakdown of the algorithm:

  1. Initialize start and end to 0, and current_sum to 0.
  2. Iterate through the array using the end pointer.
  3. Add the value at end to current_sum.
  4. While current_sum is greater than the target, subtract the value at start from current_sum and increment start.
  5. If current_sum equals the target, return the indices [start, end].
  6. If the loop completes without finding a subarray, return an empty list or indicate no solution.

Code Implementation

def find_subarray_with_given_sum(nums, target):
    start = 0
    current_sum = 0
    
    for end in range(len(nums)):
        # Add the current element to the current_sum
        current_sum += nums[end]
        
        # While current_sum is greater than target, subtract the element at start
        while current_sum > target:
            current_sum -= nums[start]
            start += 1
        
        # Check if we have found the subarray with the sum equal to target
        if current_sum == target:
            return [start, end]
    
    # If no subarray is found, return an empty list
    return []

# Example usage
nums = [1, 1, 5, 2, 1, 3, 10, 2, 1]
target = 21
print(find_subarray_with_given_sum(nums, target))  # Output: [2, 6]

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 and not any additional data structures.

Edge Cases

Consider the following edge cases:

  • An empty array: The function should return an empty list.
  • An array where no subarray sums to the target: The function should return an empty list.
  • An array where the entire array sums to the target: The function should return [0, len(nums) - 1].

Testing these edge cases ensures the robustness of the solution.

Testing

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

def test_find_subarray_with_given_sum():
    assert find_subarray_with_given_sum([1, 1, 5, 2, 1, 3, 10, 2, 1], 21) == [2, 6]
    assert find_subarray_with_given_sum([1, 2, 3, 4, 5], 9) == [1, 3]
    assert find_subarray_with_given_sum([1, 2, 3, 4, 5], 15) == [0, 4]
    assert find_subarray_with_given_sum([1, 2, 3, 4, 5], 100) == []
    assert find_subarray_with_given_sum([], 0) == []
    print("All test cases pass")

test_find_subarray_with_given_sum()

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Understand the problem requirements and constraints thoroughly.
  • Think about different approaches and their trade-offs.
  • Start with a simple solution and then optimize it.
  • Use diagrams or pseudo-code to visualize the problem and solution.
  • 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, which provides an optimal solution with O(n) time complexity and O(1) space complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: