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

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

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

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

Problem Definition

The problem requires finding a continuous subarray within a given array of non-negative integers that sums up to a specified target value. The solution should return the start and end indices of this subarray. If there are multiple solutions, any one of them can be returned.

Input:

• nums: An array of non-negative integers.
• target: A non-negative integer representing the target sum.

Output:

• An array containing two integers representing the start and end indices of the subarray that sums to the target.

Constraints:

• The input array contains only non-negative integers.
• The algorithm should run in O(n) time and use O(1) extra space.

Example:

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

Understanding the Problem

The core challenge is to find a continuous subarray that sums up to the 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 a sliding window approach. This method involves maintaining a window of elements that potentially sum up to the target. We adjust the window size dynamically by expanding or contracting it based on the current sum of elements within the window.

Naive Solution

A naive solution would involve checking all possible subarrays and their sums, which would result in a time complexity of O(n^2). This is not optimal for large arrays.

Optimized Solution

The optimized solution uses the sliding window technique:

• Initialize two pointers, start and end, both set to the beginning of the array.
• Maintain a variable currentSum to store the sum of the current window.
• Expand the window by moving the end pointer and adding the value at end to currentSum.
• If currentSum exceeds the target, contract the window by moving the start pointer and subtracting the value at start from currentSum.
• Continue this process until currentSum equals the target or the end pointer reaches the end of the array.

Algorithm

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

1. Initialize start and end to 0, and currentSum to 0.
2. Iterate through the array using the end pointer.
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].
6. If the loop completes without finding a subarray, return an empty array or an indication that no such subarray exists.

Code Implementation

/**
 * Function to find the subarray with a given sum.
 * @param {number[]} nums - The input array of non-negative integers.
 * @param {number} target - The target sum.
 * @return {number[]} - The start and end indices of the subarray.
 */
function subarraySum(nums, target) {
    let start = 0;
    let currentSum = 0;

    for (let 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++;
        }

        // If currentSum equals target, return the start and end indices
        if (currentSum === target) {
            return [start, end];
        }
    }

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

// Example usage:
const nums = [1, 1, 5, 2, 1, 3, 10, 2, 1];
const target = 21;
console.log(subarraySum(nums, target)); // Output: [2, 6]

Complexity Analysis

The time complexity of the sliding window approach is O(n) because each element is processed at most twice (once when added and once when subtracted). The space complexity is O(1) as we only use a few extra variables.

Edge Cases

Potential edge cases include:

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

Examples:

// Edge case: empty array
console.log(subarraySum([], 5)); // Output: []

// Edge case: no subarray sums to the target
console.log(subarraySum([1, 2, 3], 7)); // Output: []

// Edge case: entire array sums to the target
console.log(subarraySum([1, 2, 3], 6)); // Output: [0, 2]

Testing

To test the solution comprehensively, consider a variety of test cases:

• Simple cases with small arrays.
• Cases where the subarray is at the beginning, middle, or end of the array.
• Edge cases as discussed above.

Example test cases:

// Simple case
console.log(subarraySum([1, 2, 3, 4, 5], 9)); // Output: [1, 3]

// Subarray at the beginning
console.log(subarraySum([5, 1, 2, 3], 5)); // Output: [0, 0]

// Subarray at the end
console.log(subarraySum([1, 2, 3, 4, 5], 12)); // Output: [2, 4]

Thinking and Problem-Solving Tips

When approaching such problems:

• Understand the problem requirements and constraints thoroughly.
• Consider different approaches and their time/space complexities.
• Use diagrams or pseudo-code to visualize the solution.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find a continuous subarray that sums to a given target using a sliding window approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice:

• LeetCode: Subarray Sum Equals K
• GeeksforGeeks: Find subarray with given sum
• Coding Ninjas: Subarray with Given Sum