Uncategorized

#4. Contains duplicates

Posted by

0

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).

If we relax the constraint to:

  • Only allow positive numbers with a known upper bound (m)
  • We are allowed to modify the input

In this case, we could solve the problem in O(n) time and O(1) space -> this approach works by moving numbers to their ‘correct’ indexes (e.g. moving the number 2 to index 2 -> which would need moving the number at index 2 to its correct position). If we ever find a number already at its correct position – we know that we have found a duplicate.

#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.

How do people get started?

Posted by

0

Obviously I didn’t write. Ha-ha, what a surprise!?

Why is it so hard to build a new habit? I feel like forcing myself to do anything more than the existing routine is super hard.

How do people get started on new behaviors and then stick with them?

Maybe I am aiming too high? Instead of trying to create polished articles or well-made videos, should I focus on just producing content? Perhaps over time, I would get better at it while keeping the barrier to entry low.