Day 62: Python Longest Subarray with Target Sum - O(n) Prefix Sum & HashMap Guide (LeetCode Vibes)

#challenge #python #algorithms #datastructures

Welcome to Day 62 of the #80DaysOfChallenges journey! This intermediate challenge solves the longest subarray with exact target sum using the powerhouse combo of prefix sums and a hashmap for O(n) time, finding not just any subarray but the longest one that sums to target. It's the classic "subarray sum equals k" variant (LeetCode #560 with length twist), storing earliest prefix indices to maximize window size when a match is found. If you're leveling up from basic arrays to hash-optimized algorithms, or crushing interview problems like finding max length subarrays, this "Python longest subarray target sum" script is efficient, returns length/start/end, and perfect for extensions like multiple targets or negative numbers.

💡 Key Takeaways from Day 62: Longest Subarray Function

This task features a function that computes prefix sums on the fly, uses a dict to store earliest indices for each prefix, and updates best length on matches. It's a prefix-hash pattern: track cumulative sums, look for complement (prefix - target). We'll detail: function with prefix dict and best trackers, loop for sum update and match check, and main with input and subarray print.

1. Function Design: Prefix Dict and Best Vars Setup

The longest_subarray_with_target function initializes for tracking:

def longest_subarray_with_target(nums: list[int], target: int) -> tuple:
    """
    Return (length, start_idx, end_idx) of the longest subarray with sum == target.
    If no such subarray exists, returns (0, -1, -1).
    """

    # prefix sum -> earliest index (sum zero before start)
    prefix_index = {0: -1}
    prefix = 0         # running prefix sum
    best_len = 0       # best length found so far
    best_start = -1    # start index of best subarray
    best_end = -1      # end index (inclusive) of best subarray

Dict starts with 0:-1 for subarrays from start. Vars track max length and indices. Handles negatives fine.

2. Loop Processing: Prefix Update and Complement Lookup

Core enumeration scans:

    for i, val in enumerate(nums):
        prefix += val             # update running sum with current value

        # If we've never seen this prefix before, record its earliest index
        if prefix not in prefix_index:
            prefix_index[prefix] = i

        # Check if there's a prefix that makes [j+1 .. i] sum == target
        need = prefix - target
        if need in prefix_index:
            start_idx = prefix_index[need] + 1
            curr_len = i - prefix_index[need]
            if curr_len > best_len:           # update best if longer found
                best_len = curr_len
                best_start = start_idx
                best_end = i

    return best_len, best_start, best_end

Adds val to prefix, stores if new. Looks for need = prefix - target, computes length if found, updates best if longer. Earliest index maximizes length. O(n) time, O(n) space.

3. Main Interactive: Input Parsing and Subarray Output

Script reads nums and target:

raw = input("Enter numbers (space-separated): ").strip()
nums = list(map(int, raw.split()))

t_raw = input("Enter target sum: ").strip()
target = int(t_raw)

length, s, e = longest_subarray_with_target(nums, target)   
if length == 0:
    print(f"No subarray sums to {target}.")
else:
    sub = nums[s:e+1]
    print(f"Longest length: {length}")
    print(f"Subarray (indices {s}..{e}): {sub}")