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:
- Brute Force Approach (Naive):
- Generate all possible subarrays using two nested loops (start index
iand end indexj). - For each subarray, calculate the sum by iterating over the elements between
iandj. - 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).
- Generate all possible subarrays using two nested loops (start index
- Better Approach (Prefix Sum Optimization):
- Use prefix sums to avoid recalculating sums repeatedly.
- For each starting point
i, maintain a running sum asjmoves forward, adding new elements incrementally instead of recalculating from scratch. - Time Complexity: O(N²).
- Space Complexity: O(1).
- 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
jisXand Prefix Sum at some earlier indexiisX-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.
- Optimal Solution for Arrays with Only Positives and Zeros (Two-Pointer / Sliding Window):
- Use two pointers (
leftandright) and maintain a running sum of the current window. - Expand
rightpointer to increase sum; if sum exceeds K, moveleftpointer 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).
- Use two pointers (
- Brute Force Approach (Naive):
Detailed Methodology / Instructions
1. Brute Force (O(N³))
- For
iin [0, n-1]: - For
jin [i, n-1]: - Initialize sum = 0
- For
kin [i, j]: - sum += arr[k]
- If sum == K, update max_length = max(max_length, j - i + 1)
2. Better (O(N²))
- For
iin [0, n-1]: - sum = 0
- For
jin [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
iin [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
Category
Educational
