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

💡 Key Takeaways from Day 62: Longest Subarray Function ## 1. Function Design: Prefix Dict and Best Vars Setup ## 2. Loop Processing: Prefix Update and Complement Lookup ## 3. Main Interactive: Input Parsing and Subarray Output ## 🎯 Summary and Reflections ## 🚀 Next Steps and Resources 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. 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. The longest_subarray_with_target function initializes for tracking: Dict starts with 0:-1 for subarrays from start. Vars track max length and indices. Handles negatives fine. Core enumeration scans: 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. Script reads nums and target: Parses, calls, prints length/subarray or none. Handles empty gracefully. This longest target sum subarray uses prefix-hash to find max length efficiently. It reinforced: Reflections: Handles negatives/zeros, assumes majority exists not needed. For multiples, track all indices. Advanced Alternatives: Sliding window for positives. Kadane variant for max sum. Your subarray tip? Share! Day 62 unlocked subarray sums. In #80DaysOfChallenges? Found huge? Post! Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse COMMAND_BLOCK: 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 Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 CODE_BLOCK: 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}") Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: 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}") CODE_BLOCK: 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}") - Prefix sum power: Enables constant-time range sums. - Earliest index: Key for max length, not any match. - Hashmap optimization: O(n) for what brute O(n^2) does. - Source Code for Challenge #62: scripts/longest_subarray_target_sum.py - Main Repository: 80-days-of-challenges - Daily Updates: Twitter/X (@Shahrouzlogs)