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.

---

Summary of Tutorials/Guides Provided

• Explanation of the subarray sum problem.
• Step-by-step walkthrough of brute force, better, and optimal solutions.
• Dry run and intuition building for the prefix sum + hash map approach.
• Code implementation and complexity analysis.
• Links to prerequisite videos and problem links in the description.

---

This video is a comprehensive tutorial on solving the “Count Subarray Sum Equals K” problem with increasing levels of optimization.