Video summary

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

Main summary

Key takeaways

Educational

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

Original video