beingsde
Sign In
Back to all DSA patterns
Array / HashMap•Pattern: Prefix Sum + HashMap•Medium

Subarray sum equals K

Problem Intuition & Objective

Count the number of contiguous subarrays whose sum equals k.

Time ComplexityO(n)
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Prefix sum + HashMap: running sum enables O(1) lookup of the complement prefix sum.

Core Invariants & Edge Cases

  • prefixSum[j] - prefixSum[i] = k → prefixSum[i] = prefixSum[j] - k
  • Use a HashMap to store counts of each prefix sum seen so far
  • For every new prefix sum, look up (prefixSum - k) in the map
Previous ProblemRotate an n×n matrix in-place by 90°Next Problem Longest consecutive sequence

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.