Month: May 2024

#3 Merge Two Sorted Lists

Posted by

0

https://leetcode.com/problems/merge-two-sorted-lists/

This is fairly straightforward problem – the only tricky part being the pointer manipulation associated with any LinkedList related question – but that gets better over time with practice.

Optimal solution takes O(N) time (where N = m + n i.e. addition of the two lists) and O(1) space.

Since the two lists are sorted, we need to pick the smaller element in each iteration and move the pointer ahead for the associated list. At the end, we should not forget to pick off the remaining items from the longer list.

With Swift, using the while let loop operator does make the code a lot easier to reason about.

Valid Parentheses

Posted by

0

https://leetcode.com/problems/valid-parentheses/submissions/

The optimal solution for this one cannot be better than O(n) space – unless you are willing-to/allowed-to modify the input. Also, should that solution be considered O(1) space if you are reusing the space allocated for input?

Instead, the O(n) space optimal solution can be achieved using a stack/array to keep a record of open brackets. When we see a closed bracket – we should return false if the last open bracket is ‘nil’ or not the matching ‘type’. At the end of the loop – we should also not have any dangling open brackets – if we do, that means the sequence of brackets was not balanced – and we should return false.

Edit: Let’s say, that the problem states the input string could only contain one of ‘(‘, ‘[‘, “{” types – in that case we can keep a single integer var openBrackets that we increment when we see a open bracket and decrement when we see a closed one. At any point if openBrackets becomes negative we know that the sequence was unbalanced, similarly, at the end of the loop, openBrackets should be 0 for the string to be balanced. This is O(1) space solution since we do not need a stack/array to keep a track of open brackets.

2 Sum

Posted by

2

https://leetcode.com/problems/two-sum

Probably the first problem you solved when you started leetcoding.

This is a classic problem – I haven’t been asked this problem ever in an interview – but this one brings back a lot of memories and yes there was a time I struggled to solve this problem as well 🙂

Using 2 loops would be the most straightforward but slow way to solve this problem – in an interview, the interviewer will expect a better solution that O(N^2) though.

The optimal solution uses a hashmap to keep the index of previously seen numbers – this increases the space complexity to O(n), but improves the time complexity to O(n).

Variant: Although this problem asks for the index of the two numbers that add up to target – there is a variant of this problem that asks for the actual numbers itself (i.e. find the two numbers that add to target). That variant can be solved in O(n logn) time, if we cannot/do-not want to allocated O(n) space – that solution first sorts the input array and then iterates over the sorted array with two pointers – increasing the left pointer if the sum is smaller and reducing the right pointer if the sum is larger than the target.

If you just solved this problem on your own – welcome to leetcoding, you have an exciting journey ahead of you.

Grind 75

Posted by

0

Although I have done most of the questions from this list while preparing for interviews in the past, I am going to revisit this series again over the next few weeks.

For two reasons:
#1. I want to start making YouTube videos – this series of questions seems like a good idea since I can focus on the video making part and not worry about the content much.
#2. It would be a good prep primer as I start preparing to enter the market again.

Let me know if you have feedback on the content I create – it would good to hear back on what I could improve as I start learning the art of video making.