Posts

DFS intuition First we must build a graph where airports are vertices and an edge airport1 -> airport2 denotes that the person travelled from airport1 -> airport2 To find a valid sequence of vertices/airports that covers all the edges/tickets, we traverse the graph using depth first search like traversal. The idea is: At each vertex, move to the next lexicographically smallest vertex. delete the edge used To maintain lexicographical order, we sort the neighbours of each vertex lexicographically. ...

Below is my solution for the leetcode 154: Find minimum in rotated sorted array problem Intuition Fact is, that you cannot solve this question in O(log n) time. The reason is because of duplicates. Consider a situation like: $$ [2,2,2,2,1,2,2] $$ where mid is at 3 and the minium number here is clearly $$1$$. But our binary search algorithm will not be able to figure out in which direction it should go, since starting, ending and middle values are all same. In this case the best we can do is increment mid which makes the worst running time: O(n) ...

Here’s my solution to the Leetcode 315: Count of Smaller Numbers After Self problem using standard merge sort. I just change one line to count while merge procedure. Solution Let’s build the solution step by step. Input: nums = $$[5,2,6,1]$$ First, turn the numbers into [number, index] tuple. So it looks like: array = $$ [ [ 5, 0 ], [ 2, 1 ], [ 6, 2 ], [ 1, 3 ] ] $$ ...

Here’s my explanation for the leetcode 306: Additive Number problem Additive Number Problem Problem Recap An additive number is a string of digits where the sequence of numbers formed by splitting the string satisfies the condition that each number (after the first two) is the sum of the two preceding numbers. Examples: "112358" is additive because the sequence is 1, 1, 2, 3, 5, 8, and: 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 "199100199" is additive because the sequence is 1, 99, 100, 199, and: ...

Here are all possible solutions I could come up with for the longest increasing subsequence problem. leetcode 300 Approach 1: Generate all possible increasing subsequences We will keep track of a subsequence in an array named cur_subsequence or cur_sub. For each element (a[i]) we have the following 2 options: Add the element to the end of current subsequence. Note: The current element can only be included if either the current subsequence is empty or the last element of the current subsequence is smaller than the current element. This is important to maintain the increasing subsequence property. ...