Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #560 Subarray Sum Equals K. The problem provides an array of elements and an integer k, with the expected return of an integer that represents the number of subarrays that can be made with a sum of k.
My initial instinct was to try and use some sort of sliding window to solve the problem, but I quickly found myself unable to do so due to the inclusion of negative numbers making the task essentially impossible.
The solution used a hashmap, similar to Contiguous Arrays. On a logical level, we know that a running sum at the end of an array will be equal to the sum at the beginning, plus the sum of the array itself. Thus we cache the beginning sum of each element, then at each index we see if there is a corresponding beginning sum. We add the frequency of that sum, because for each beginning sum instance, we are able to create a unique subarray. This allows us to solve the problem in O(n) time and O(n) space.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/16 hours per week, [109/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion
20:38 - Coding Begins (Attempt at Sliding Window)
30:52 - Solution Discussion (Hashmap)