Summary of "Count Subarray sum Equals K | Brute - Better -Optimal"

Summary of “Count Subarray Sum Equals K | Brute - Better - Optimal”

This video is part of the Striver’s A to Z DSA course, focusing on solving the problem: Count the number of subarrays whose sum equals K. The problem requires understanding what a subarray is (a contiguous portion of the array) and finding all such subarrays summing to a target K.

Problem Explanation

Subarray definition: Any contiguous part of the array (single element, multiple consecutive elements, or the entire array).
An example is given with an array and target sum K = 3, illustrating multiple subarrays that sum to 3.
Important distinction between subarray (contiguous) and subsequence (non-contiguous).

Solutions Covered

1. Brute Force Approach (Naive)

Generate all possible subarrays using three nested loops:
- Outer two loops select start and end indices (i, j).
- Inner loop sums elements from i to j.
Time Complexity: Approximately O(n³).
Space Complexity: O(1).
Inefficient for large inputs; generally not acceptable in interviews.

2. Better Approach (Prefix Sum with Two Loops)

Avoid the inner summation loop by maintaining a running sum while extending the subarray.
For each start index i, move end index j forward and keep adding elements to the sum.
Check if the sum equals K.
Time Complexity: O(n²).
Space Complexity: O(1).
Still not optimal; interviewers may ask for further optimization.

3. Optimal Approach (Prefix Sum + Hash Map)

Use prefix sums and a hash map to store frequencies of prefix sums encountered.
Key insight:
- If prefix sum at index j is s and you want subarray sum = K, then check how many prefix sums equal to s - K have appeared before.
- Each occurrence corresponds to a subarray ending at j with sum K.
Algorithm:
- Initialize prefix_sum = 0, map with {0:1} (to handle subarrays starting from index 0).
- Iterate through the array, update prefix sum.
- Check if prefix_sum - K exists in map; if yes, add its count to the answer.
- Update map with current prefix sum frequency.
Time Complexity: O(n) on average (due to hash map operations).
Space Complexity: O(n) (for storing prefix sums in the map).
This method is the most efficient and preferred solution.

Additional Notes

Storing prefix sum zero initially is important to handle cases where the subarray starts at the beginning.
The video provides a dry run of the optimal solution to build intuition.
It encourages watching prerequisite videos on prefix sums for better understanding.
Code implementation is succinct (about 4 lines) once the logic is understood.
Discussion on hash map complexities:
- Average case: O(1) per operation.
- Worst case: O(n).
- Alternatives like balanced trees offer O(log n) complexity.

Key Takeaways

Understanding the difference between brute force, better, and optimal solutions is crucial.
The prefix sum + hash map technique is a powerful pattern for subarray sum problems.
Efficient coding and problem-solving require recognizing patterns and using appropriate data structures.
The video is part of a comprehensive DSA course with 455 models and 400+ problems.

Main Speaker / Source

The video is presented by Striver, a popular educator known for in-depth Data Structures and Algorithms tutorials.
The content is from the Striver’s A to Z DSA course.