-
Notifications
You must be signed in to change notification settings - Fork 0
Day 41 to 50
Not too sure how to feel after that one. 🤔
My working solution came out as O(n log m), but it could have been done in O(n + m) with the use of sets. This is because Array to Set conversion will take O(n) time (O(n + m) for two arrays), but then set lookups can be done in constant time (O(1)) because they are implemented with a hash table. Of course. The problem being under Binary Search did throw me off though so I thought that had to be incorporated somehow. Although I should have realized it could have been done quicker this way. At least now I know. Sets (can) have constant lookup!
Glad to see I learned from the optimal solution from last time!
More or less the same technique, but with the direct use of a hash and not sets. This method is a prime example of the Space–time tradeoff though, so resorting to it when memory is limited won't always work.
Two Sum II - Input array is sorted
I couldn't stop myself from grinning when I saw that this would be my problem for the day. 😁
Have actually already been asked to whiteboard this at an interview. And the long and short of it is I made it out alive and it was the best internship experience ever! 😂 But regarding the problem itself, the naive way to do it – and my first instinct during the interview – would be an O(n²) solution. There is, however, a way to do it in O(n) time with two pointers and the right conditionals. This is what I implemented here!
Déjà vu. 😅 Again came up with a O(n log n) solution using Binary Search when I could have done it in O(n) with a Set.
The Set solution was definitely more obvious, but I think I was trying to be too clever. I forgot that sorting an array – which was required by the first part of my solution – would cost O(n log n) and not just O(log n). Same problem as with before again though: that the Set way would be more expensive space-wise whereas the Binary Search solution could be achieved in constant (O(1)) space if the sorting of the array were done in place. Again, a classic case of Space–time tradeoff.
A solution having to do with Cycle Detection was also brought up boasting the best of both worlds, space- and time-wise, but I'm too sleepy right now to process it. 😴 Might take a look again tomorrow or this weekend.
Quite an easy problem to solve conceptually. I knew almost instantly what my approach would be after reading it.
There were very many edge cases though given the implementation I was going for. I didn't want to resort to operating directly on the given lists, so I worked with index pointers instead. That solution forced me toward more if-else blocks than I would like. Nonetheless, I completed a solution that would run in O(n + m) time as had been asked.
Find K-th Smallest Pair Distance (In Progress)
This one is quite an interesting problem. Has really had me thinking and will definitely keep me thinking over the weekend.
I thought to try a naive solution first since I wasn't really sure if there exists a faster way. That attempt timed out though, so that means there is still room to optimize. Right now, my run time is O(n² + n log n). The first term is me generating all the pairs and the next is having to sort the distances. I think generating all the pairs is a requirement, so I might have to look at optimizing out the second term.
Correction: The run time for my initial solution was O(n² log n).
Find K-th Smallest Pair Distance (In Progress)
Still have yet to solve this one, but glad to have encountered this problem!
Learning a lot from this experience thanks to my friend, @Hikari9, namely that it's okay to read solutions if I'm stuck (which I did) and that Python code generally runs quite slowly (which surprised me). The latter also forced me to rewrite my solution in Java, which I legitimately have not touched in years (and it was syntax error hell). But when my code finally did compile and run, I ran across a Memory Limit Exceeded error. 😅
Am currently implementing a not-in-place quickselect solution, so will probably try for an in-place version tomorrow.
Find K-th Smallest Pair Distance
Definitely one of the hardest problems I've come across on this journey so far!
Unfortunately, even an in-place quickselect solution, like I was trying to do initially, would have run into Memory Limit Exceeded errors, so I instead tried implementing one of the Binary Search solutions brought up in the problem discussion board. That solution forced me to reframe my thinking in terms of Binary Search again. I nearly forgot the three templates, but I was able to see this one was of the Template II variety! It all became clearer for me after that. Hoping I'll better be able to recognize these types of problems in the future!
Split Array Largest Sum (In Progress)
Haven't yet been able to give too much time to this, but I think I've come up with a possible Binary Search solution.
It will (might?) work this way:
- First, evenly divide the array into m contiguous subarrays.
- Get the sum of each of the subarrays and find the average among all sums.
- For each index that split the array into subarrays, move it left or right by Binary Search until it comes as close as possible to the average we got earlier.
- When you reach the end, determine which subarray has the least sum and return that.
No clue if this will work, but it's the best possible solution I have in my head right now. Will try to implement it tomorrow.
Again, another quite difficult problem. Had to refer again to the solution to get this one.
Still not 100% on how it works. I understand what's going on with the algorithm at a high level, but I need and want to dig into its details to see exactly why it is able to find the answer we're looking for. One interesting thing I did learn from this problem and looking through a few solutions is how most problems can be broken down into distinct subproblems that, when solved together, sum up to a solution to the bigger problem. Interesting stuff.