-
Notifications
You must be signed in to change notification settings - Fork 0
Day 31 to 40
A bit deflated after that solve if I'm being honest. Took too many submits and, in the end, it turned out my solution wasn't optimal. 😢
I appropriated an empty conference room at my office earlier to try to figure this out and I came up with an O(n) solution. (It was good practice for a whiteboard interview, though I wasn't really thinking out loud.) I thought that it was going to be enough – and technically it was – to finish in time, but it turns out there exists an O(log n) solution so I will spend the day tomorrow revisiting the problem to try to figure it out!
A fresh start will help clear my mind!
Find K Closest Elements (Study)
This is the first day I'm not attempting to work on a new problem or one I haven't yet solved.
And I absolutely think it was every bit as productive if not more so than any of the other days I have been solving problems. I really learned a lot carefully studying the sample solutions – about time complexity, different techniques, and different ways of thinking. I also found that the solution I came up with was what most others worked out too (which was comforting). And that the optimal solution was really an outlier, but one I will continue to aim for.
Pow(x, n) (In Progress)
This is one of those problems right now I have almost zero clue on how to solve.
Not much to write about other than that I guess. It seems to need some kind of Math trickery I just might not know, so I'm not sure how much use there is for me to sit on the problem. Will give it another day I guess, then well, we'll see. 🤷♂️
Pow(x, n) (In Progress)
Opened up a Wiki page to help me make sense of the problem (or more the math, really).
I found the solution and it's something called Exponentiation by squaring. There's pseudocode for the algorithm, but I'm trying not to just copy it. Want to at least be able to write it from my understanding of the math – and right now I'm proving unsuccessful. 😅 Bit sleepy and (too) frustrated at this point. Will leave it for tomorrow!
Returned to the problem first thing at work and finally settled on the recursive solution.
Based on the Exponentiation by squaring Wiki page I was reading last night, I had kept trying to implement an iterative version. I think though that the approach denoted by the formula might not have had an iterative implementation – and reading through a few of the iterative approaches, it seems those did have a different approach entirely. I guess I kept trying to force myself through a wall last night where there was no opening. 😅
I managed to write the recursive solution with relative ease though. It translates much nicer from the formula I had been looking at. Though I wish I hadn't basically shown myself the solution beforehand. I wonder if I still would have gotten it as easily. My consolation though is I at least understand the math.
Maybe one of my easiest solves so far on my #100DaysOfCode journey. I think the LeetCode gods threw me a bone after they knew I had so much trouble with the last one. 😅
This one was Binary Search in its purest form – and very similar to the Sqrt(x) problem I tackled from Days 19–20. Good to have seen I learned from that previous experience. Previously, I needlessly built a list and operated over that to perform the Binary Search. But now, I consciously stopped myself from taking a similar approach because I knew that it would be slower (not from a Big O standpoint, but just by raw speed).
Find Smallest Letter Greater Than Target
Another not-so-difficult one!
Again, almost a direct application of one of the 3 templates of Binary Search – in this case Template III. I'm thankful for these review problems though because I realized I didn't really understand the templates until just 3 or 4 problems ago. Going over these helped me reinforce what learnings I should have had when the templates were introduced to me in the first place. 😅 But I understand now the differences between the three in their terminating condition, search narrowing logic, and need for post-processing (or lack thereof)! 🎉
Find Minimum in Rotated Sorted Array II (In Progress)
This one is a variant of the Day 27 Problem.
I have a solution right now passing 185/192 test cases. Not quite there yet, but proud that it is much shorter than my solution to the problem from before. Definitely comes from now understanding the Binary Search templates! 😅 There is an edge case I'm missing though, which I think will push the runtime beyond just O(log n), and up to maybe O(n). 🤔
Find Minimum in Rotated Sorted Array II
Not quite sure why, but this was one hell of a satisfying solve. Maybe cause I had put it off for about 3 days, so it felt as if a weight had been lifted off my shoulders.
Anyhow, it looks like my hunch was right. Average case is O(log n) – worst case O(n). My previous submission was not too far off. Just needed to handle the worst case scenario. Want to add that I came up with a nice way to visualize this problem and it definitely helped me formulate my solution. Maybe given as how I am quite a visual learner, I ought to try to make a diagram of the problems as I attempt to solve them.
Intersection of Two Arrays (In Progress)
Have spent more time so far thinking about this one than writing code to solve it.
Thought I had an answer already, but came out with a solution for computing the union of two arrays rather than their intersection. 😂 Might have been the long week. Anyway, I do think I know how to do it in O(n log n) time on average:
- Sort each list
- Iterate over the shorter list and for each number, binary search for the same number in the second list
- If found, append it to another array for storing the intersections, otherwise, just continue iterating
- When you reach the end of the shorter list, your array should have the intersection of the two arrays