Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #525 Contiguous Array. The problem provides an array of integers, with the expected output of an integer that represents the length of the longest subarray that can be created which has the same number of 1s and 0s.
This problem stumped me (as will the one coming later in the day). I intially thought that a sliding window approach could work, but quickly ruled that out as there wasn't any really good way to know which items that our subarray would eventually cover. In the absence of that, a brute force method would have been too slow.
I also thought about dynamic programming, including using a "score" where 0 increments and 1 decrements, but couldn't come to a clean solution. Looking at the answer provided by LeetCode, it turns out that I was partially correct - the main key here is that when we reach a "score" that we have already achieved, we know that we can build an array of balanced 1s and 0s because the only way for the same score to occur is if there were an equal number of increments/decrements to reach that score. We use a hashmap to keep track of the score, and then return the maximum. This takes O(n) time, and O(n) space, where n is the number of elements within our array.
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, [101/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion
30:03 - Solution Discussion (Hashmap)