Some DSA problems just _click _— they remind you why problem-solving feels so satisfying.
Today’s one was exactly that:
“Find the largest or smallest subarray whose sum equals K.”
**
At first glance, it looks simple. But once you dig in, you start seeing the beauty of how **logic and data structures work together.
*💭 My First Thought: Brute Force It
*
I started with the most obvious approach — two nested loops.
For every starting point i, I extended the subarray until j _and checked if the sum matched _K.
Whenever it did, I updated the max/min length.
It worked… but it wasn’t efficient.
As soon as the array got large, performance dropped fast.
Time complexity? O(N²) — not great.
But honestly, brute force is always my warm-up round. It helps me understand the pattern before optimizing.
⚙️ The Aha Moment: HashMap + Prefix Sum
**
Then came the real game changer — **prefix sums and hashmaps.
Instead of re-summing elements again and again, I stored cumulative sums.
At each index j, I looked for a previous prefix sum p[i-1] such that:
p[i-1] = p[j] - K
If it existed, that meant the subarray between (i, j) had a sum of K.
With that, I could instantly calculate the subarray length and update my max/min lengths — all in O(N) time.
Honestly, it felt _magical _ to watch the brute force approach melt into something elegant.
****🧠 Key Takeaways
Brute force teaches intuition. Always start there — it helps you understand the logic.
Prefix sums + hashmaps are super powerful for subarray and range problems.
The best feeling? Watching your O(N²) solution drop to O(N). 😄
*💬 Final Reflection
*
This problem was more than just about arrays and math — it was a lesson in pattern recognition and problem simplification.
Every DSA challenge like this builds that “aha!” muscle a little stronger.
I coded it in **
**, but honestly, the concept stays the same in any language.
If you haven’t tried this one yet — give it a go!
Top comments (0)