Hacky Coding: Coding as a Non-Coder — Nested Arrays
As I gain more and more experience in the crazy world of algorithms, I sometimes sit back and wonder how I would’ve solved these problems if I weren’t a programmer. I remember my brain using binary search at the guessing game(where you guess a number within a range and if you get it wrong, you get a hint on whether your guess is too high or too low), before I even knew what binary search was, let along how to code it!
Now, what if I approach an algorithm problem with some lovable derp? When I first look at a problem, instead of immediately thinking about similar patterns from older problems I’ve seen or language methods, what if I were to solve this assuming I have zero algorithm experience? So let’s start thinking about that. Intuitively, how does our brain solve these problems?
Let’s look at the arrayception problem!
Given an array of arbitrarily nested arrays, return n, where n is the deepest level that contains a non-array value.
input: [ [ 5 ], [ [ ] ] ]
input: [ 10, 20, 30, 40 ]
input: [ [ 10, 20 ], [ [ 30, [[[]] ] ] ] ]
input: [ ]
input: [ [ [ ] ] ]
input: [[], [[[[[[[]]]]]]], ]
The engineer in me would have looked at this problem and think, oh, this is a recursion problem. And I would’ve come up with the below:
But, thinking as a non-coder, I would have just counted the brackets. Wait, what?! Yep. Intuitively, my eyes would just scan the entire input and see what is the longest unmatched open bracket (because once we see a closing bracket, it means we are popping out one level of nested array. In other words, I am looking at the input as a whole, instead of thinking it as an array. After all, non-coders wouldn’t know what an array is.
Great, now I can just traverse this string instead and keep track of my open and close brackets. There are three possible types of characters in my string, [, ], or anything else. If I keep a counter of my [’s, and decrement it when I reach a ], I can find the longest unmatched [’s! The way to keep track of this max value would be to check my counter every time I reach anything other than [ or ]. Let’s look at this hacky code I came up with below. I don’t want to check the counter when I hit a ] because I don’t want to keep track of empty arrays.
Hacky Code (gist)
It passes all test cases! And Isn’t traversing a string much easier to write recursion?
Now, this is the time to think like a coder for a bit: runtime complexity. The function would run with O(n) time since there is only one for loop. Even though recursion has a the same Big O, iteration performs slightly faster than recursion because recursion has higher overhead. However, since you could be traversing waaaaaaaaaay more elements than the original array elements, this is an absolute terrible solution.
So, what is the purpose of this? Well, really it’s just to explore my curiosity as I try to think outside the box and see what I can come up with. And I was pleasantly surprised that it worked! Training my brain to think in ways it was not taught to think can be eye opening and I just wanted to see what’s possible.
And after all, it was fun.
Now, what if you need to flatten an array…?
— love, Kaisin