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.

https://leetcode.com/problems/contains-duplicate/

This one always tricks me – even though the problem is really straightforward, I have spent a lot of time trying to find a solution better than O(n) time.

But given the constraint -> -109 <= nums[i] <= 109 – optimal solution cannot be better than O(n) time. Also, the optimal solution ends up being O(n) space as well, since we have to use a Set or a Map data structure to record previously seen numbers.

If we can’t allocate O(n) space: there are two possible solutions. One approach could be to use two loops -> select a number and check if that numbers appears again in the rest of the array -> this would be a O(n^2) solution.

The other solution first sorts the input (which would take O(n logn) time) and then iterates over the sorted array to detect equal neighbors. Swift uses Timsort -> which takes O(n) space, but we could implement selection sort which runs in O(1) space – however I would not expect that in an interview (hopefully).