Subarray with Given Sum
Sliding Window Algorithm Explained

def subarray_brute(arr, target):
    n = len(arr)
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]
            if current_sum == target:
                return i, j          # found!
            if current_sum > target:
                break               # no need to go further
    return -1, -1

Window starts: [2]          → sum = 2, too small, expand
Window now:    [2, -1]      → sum = 1, still small, expand
Window now:    [2, -1, 2]   → sum = 3, MATCH? Yes!

But wait — what if target = 2?
Window:        [2]          → sum = 2, MATCH... but we'd miss it
Window:        [2, -1, 2]   → sum = 3, too big, shrink left
Window:        [-1, 2]      → sum = 1, too small, expand again...
The shrink/expand logic fails with negatives!

def subarray_prefix(arr, target):
    prefix_map = {0: -1}   # maps prefix_sum → index
    current_sum = 0

    for i, num in enumerate(arr):
        current_sum += num

        # Check if (current_sum - target) was seen before
        if (current_sum - target) in prefix_map:
            start = prefix_map[current_sum - target] + 1
            print(f"Subarray found: index {start} to {i}")
            return start, i

        prefix_map[current_sum] = i

    return -1, -1

FUNCTION findSubarrayWithSum(arr, target):
    left  ← 0
    right ← 0
    sum   ← 0

    WHILE right < length(arr):
        sum ← sum + arr[right]       // expand window

        WHILE sum > target AND left < right:
            sum ← sum - arr[left]    // shrink window
            left ← left + 1

        IF sum == target:
            RETURN (left, right)     // found!

        right ← right + 1

    RETURN (-1, -1)                  // not found

def subarray_sliding_window(arr, target):
    """
    Find subarray with given sum using sliding window.
    Works ONLY for arrays with positive integers.
    Time: O(n), Space: O(1)
    """
    n = len(arr)
    left = 0
    current_sum = 0

    for right in range(n):
        # Expand window by adding right element
        current_sum += arr[right]

        # Shrink window from left while sum exceeds target
        while current_sum > target and left < right:
            current_sum -= arr[left]
            left += 1

        # Check if we found our target
        if current_sum == target:
            print(f"Subarray found: index {left} to {right}")
            print(f"Subarray: {arr[left:right+1]}")
            return left, right

    print("No subarray found with given sum")
    return -1, -1

# ── Driver Code ──
if __name__ == "__main__":
    arr = [1, 2, 3, 7, 5]
    target = 12
    subarray_sliding_window(arr, target)
    # Output: Subarray found: index 2 to 4 → [3, 7, 5]

def subarray_prefix_sum(arr, target):
    """
    Find subarray with given sum using prefix sum + hashing.
    Works for ANY array including negative numbers.
    Time: O(n), Space: O(n)
    """
    prefix_map = {0: -1}   # prefix_sum → index mapping
    current_sum = 0

    for i, num in enumerate(arr):
        current_sum += num   # accumulate prefix sum

        # If (current_sum - target) was seen before → subarray exists
        needed = current_sum - target
        if needed in prefix_map:
            start = prefix_map[needed] + 1
            print(f"Subarray found: index {start} to {i}")
            print(f"Subarray: {arr[start:i+1]}")
            return start, i

        # Store this prefix sum for future lookups
        prefix_map[current_sum] = i

    print("No subarray found")
    return -1, -1