Summary of Longest Subarray with sum K | Brute - Better - Optimal | Generate Subarrays

Summary of "Longest Subarray with sum K | Brute - Better - Optimal | Generate Subarrays"

---

Main Ideas and Concepts

• Problem Statement:
  Find the longest contiguous subarray (subarray = contiguous part of an array) whose elements sum to a given value K.
  Important: The subarray must be contiguous, not just any subsequence.
• Understanding Subarrays:
  • A subarray is a continuous segment of the original array.
  • Examples given to clarify what counts as subarrays and what does not.
  • Length of subarray = (end_index - start_index + 1).
• Approaches to Solve the Problem:
  1. Brute Force Approach (Naive):
     • Generate all possible subarrays using two nested loops (start index i and end index j).
     • For each subarray, calculate the sum by iterating over the elements between i and j.
     • Track the longest subarray whose sum equals K.
     • Time Complexity: O(N³) due to three nested loops (two for subarray generation, one for sum calculation).
     • Space Complexity: O(1).
  2. Better Approach (Prefix Sum Optimization):
     • Use prefix sums to avoid recalculating sums repeatedly.
     • For each starting point i, maintain a running sum as j moves forward, adding new elements incrementally instead of recalculating from scratch.
     • Time Complexity: O(N²).
     • Space Complexity: O(1).
  3. Better Solution Using Hashing (Prefix Sum + Hash Map):
     • Use prefix sums and a Hash Map to store prefix sums and their earliest indices.
     • Key insight: If Prefix Sum at index j is X and Prefix Sum at some earlier index i is X-K, then the subarray (i+1 to j) sums to K.
     • For each Prefix Sum, check if (prefix_sum - K) exists in the Hash Map. If yes, update max length accordingly.
     • Store prefix sums only once (first occurrence) to maximize subarray length (leftmost Prefix Sum).
     • Handles arrays with positive, negative, and zero values.
     • Time Complexity: Average O(N), but worst case can degrade to O(N²) due to hash collisions (especially if using unordered maps).
     • Space Complexity: O(N) for storing prefix sums in the Hash Map.
  4. Optimal Solution for Arrays with Only Positives and Zeros (Two-Pointer / Sliding Window):
     • Use two pointers (left and right) and maintain a running sum of the current window.
     • Expand right pointer to increase sum; if sum exceeds K, move left pointer to reduce sum.
     • Whenever sum equals K, update max length.
     • This approach leverages the property that sum increases when moving right pointer forward (only positives and zeros).
     • Time Complexity: O(N) because each element is visited at most twice (once when expanding right, once when shrinking left).
     • Space Complexity: O(1).

---

Detailed Methodology / Instructions

1. Brute Force (O(N³))

• For i in [0, n-1]:
• For j in [i, n-1]:
• Initialize sum = 0
• For k in [i, j]:
• sum += arr[k]
• If sum == K, update max_length = max(max_length, j - i + 1)

2. Better (O(N²))

• For i in [0, n-1]:
• sum = 0
• For j in [i, n-1]:
• sum += arr[j]
• If sum == K, update max_length = max(max_length, j - i + 1)

3. Better Using Hashing (Prefix Sum + Hash Map)

• Initialize Hash Map: prefix_sum_map = {}
• Initialize sum = 0, max_length = 0
• For i in [0, n-1]:
• sum += arr[i]
• If sum == K, max_length = i + 1 (subarray from start)
• If (sum - K) in prefix_sum_map:
• length = i - prefix_sum_map[sum - K]
• max_length = max(max_length, length)
• If sum not in prefix_sum_map:
• prefix_sum_map[sum] = i (store earliest occurrence)
• Return max_length

Note

Notable Quotes

— 01:13 — « Just keep this in your mind when I say subarray it means contiguous, very very important word contiguous part of the array. »

— 38:03 — « The time complexity at worst case is big O of 2N. The right pointer runs till n, and the inner while loop runs overall for n iterations across the entire process, so total is about 2N. »

— 40:35 — « If you tell this entirely to the interviewer, he will be super duper impressed. »

Category

Educational

Video