https://leetcode.com/problems/min-stack/

The problem asks us to extend stack’s API – so that in addition to being able to return the top, we can also look up the minimum number.

The most straightforward (and inefficient solution) would be to keep a separate store that mimics operations on the main stack – but instead of storing the actual values, this stack would only store the minimum at the top – comparing each newly inserted value with the current min. The obvious problem with this solution is the fact that we are wasting space by possibly repeatedly inserting the same value into the stack.

Instead, we should only insert into the minStack if the current value happens to be lesser than current min. When we pop, we need to update the minStack variable if the value being popped is the current min. This gives us O(1) time and O(n) space solution – note that the space complexity still stays at O(n) since in the worst case (when the numbers are sorted in descending order), we would still end up duplicating every value twice in both data structures.

https://leetcode.com/problems/3sum/

I always struggle with this problem 🙂

Even when I have solved it multiple times – the reasoning behind the solution is simple enough, the tricky part for me is always getting rid of duplicates.

The basic idea is simple – choose one number and then try to find two additional numbers such that all three numbers combined – their sum is 0.

Now, with 2 Sum solved – we already know how to find two numbers that add up to a specific number (in this case, target – firstNumber). So the trick to this question is to first choose a number and then use the 2 Sum solution to find the other two numbers.

It is possible to solve this without sorting, but I find sorting + two pointer approach much simpler to reason and code in an interview setup.

So my solution – sorts the array first, ‘chooses’ a non-duplicate number as possible part of triplet – and then tries to find two more numbers (by using two pointer approach) that add up to 0. If we do find a triplet that meets the criteria – we need to be careful to ignore all neighbors that are the same number.

This gets us the O(N^2) time solution. Based on the language used, the time complexity varies, however Swift sort uses tim sort which takes O(N) space to sort an array.

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Again, a straightforward question. If you are not using the fact that the numbers are sorted – you are doing it wrong.

With 2 sum, since the numbers were not sorted, we had to use a Dictionary/Map to get the optimal solution.

But since the numbers are sorted in this question, we could use two pointers (left and right), to get a O(n) space and O(1) time solution.

https://leetcode.com/problems/valid-palindrome/

This is a relatively straightforward question – converting the string to an Array makes it easier to iterate over characters with two pointers – however that solution would take O(N) space.

Instead, we could use the .startIndex, .endIndex properties, along with the index(after:) and index(before:) methods of String struct to achieve a O(1) space, O(N) time solution.

https://leetcode.com/problems/daily-temperatures

Brute force solution can be achieved in O(N^2) time – for each ‘index’ this would required looking at all temperature that come after ‘index’ – if any temperature is higher than temperatures[index] – we have a warmer day.

Logically this should come to you fairly quickly during an interview – coding this up in 10 minutes or is less is possible as well.

However I really struggled with the O(N) solution – and I am not sure if it can be achieved unless you know about monotonic stacks before you see this problem.

For an O(N) time solution, for each temperature we see along the way, we must be able to find a ‘colder’ day right before that temperature. Basically for each temperature, we want the ‘next’ smaller temperature – and this is what monotonic stacks are amazing at.

For this to work, we need a stack that stores temperatures in a ‘decreasing’ order from bottom to top – such that the element at the top is smallest. So when we see a temperature that is warmer than than stack top -> we know that we have found a day warmer than stack top. When this happens, we need to keep popping the stack till the top of the stack is warmer than ‘current’ temperature. Once done, when we insert the current temperature to stack – the stack still stays sorted in increasing order from top to bottom.

Like I said, I struggled with this problem – but knowing how monotonic stack works now, I think I should be able to solve other questions in future that need ‘next’ smaller or larger element to get the optimal solution.

https://leetcode.com/problems/product-of-array-except-self/

Not a fan of this question 🙂

It is a bit tricky to code up the first time – but there is nothing logically difficult about it, so not really sure why a company might choose to ask it in an interview.

If we could use ‘/’ operator, the solution would be straightforward -> result[i] = (total_product)/a[i].

One possible appraoch -> result[i] = left_product[i] * right_product[i].

We could achieve this by creating two arrays one for left_product and another for right_product, but this could also be solved in O(1) space (not considering the memory required for returned array) by using a single array that first stores right_products and then overwrites the same array with final answer.

https://leetcode.com/problems/encode-and-decode-strings/

I was asked this in an interview – don’t remember the company now, but I do remember struggling to solve it 🙂

If you cheat – this becomes a very easy problem to solve. By cheat I mean you could just use a character not present in the standard 256 ASCII list as your ‘marker’. To decode, you could just split the string (swift string.split weirdly filters out empty strings – which fails the test cases set for this problem. So instead we have to iterate and match each character to the ‘marker’) by using the marker and you would get back the original string. Most interviewers would not accept the solution – simply saying what if we wanted to extend the support to other characters in the future?

So to make the solution more generalized, we have to come up with a better strategy. Leetcode’s solution set covers some of them.

The strategy I used, encodes the string by writing its length along with a marker before the actual string e.g. hello would be encoded as “#5#hello”. While decoding, I wait for “#” to be read – after that I try to read a number till I find the next “#” – once I know the length of the upcoming string – reading that string becomes fairly straightforward.

In my first attempt I tried to encode using the pattern “#5hello” -> but this breaks for strings that start with a number e.g. 1word -> this would be encoded as #51word -> this breaks the decoding since we could not infer correctly if the upcoming string is of length 5 or 51. But using #length#string pattern fixes that issue.

https://leetcode.com/problems/top-k-frequent-elements/

I love this problem – its not that hard to solve sub-optimally, but the optimal solution is super elegant.

Counting frequency of each number and then sorting the array by the frequency of each number would be the most straightforward approach – but there are multiple ways of doing that!

#1. Simple sort:
Count the frequency of each number. Create an array of pairs -> {number, count} -> sort this array of pairs using the frequency. Return the first k results of this sorted array. This would be fairly easy to code up within 15 mins or so in an interview. However, this would be O(n log n) since we are sorting the entire array – when in fact we only need the first K elements.

[#2. Min heap] -> This only works if your language has a min heap data structure. Swift does not, and I would not venture coding one up during an interview. But this is a neat solution to propose since it fixes the issue with the first approach – instead of sorting the entire array, this solution uses a min heap to pop the current ‘least’ frequent number – since the heap does not grow beyond size k – we improve the time complexity to O(N log k).

#3. Bucket sort – by far the best solution. The key insight here is the fact that the frequency of any number cannot be higher than N -> this allows us to use an Array to store numbers at an index equal to their frequencies. Which also means we do not need to sort – instead we can just reverse iterate the array – the numbers with maximum frequency will be stored at the back of the array. And just like that we have a O(N) solution.