Posts

The idea is to keep 2 pointers. trail pointer and cur pointer. The list is build in recursive function build(trail, cur) which returns last node of the list we build. build works as follows: when there is no child node: simply connect trail and cur and advance both when there is a child node, then recursively call itself with build( trail = cur, cur = cur.child ). The call would connect cur node with the list in the next level. It would return the last node in next level. Then we assign trail = last node in next level and cur = cur.next in current level. This ensures that the next iteration would connect last node in next level to next node in current level. when cur becomes null trail is the last node in current level. return trail Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 function flatten(head: _Node | null): _Node | null { const save: _Node = new _Node( -1 ); build( save, head ); if ( save.next ) save.next.prev = null; return save.next; }; function build( trail: _Node | null, cur: _Node | null ): _Node | null { while ( cur ) { if ( !cur.child ) { trail.next = cur; cur.prev = trail; trail = trail.next; cur = cur.next; } else { trail.next = cur; cur.prev = trail; const saveNext = cur.next; const lastNodeFromChildList = build( cur, cur.child ); cur.child = null; cur = saveNext; trail = lastNodeFromChildList; } } return trail; } Complexity Time complexity: $$O(n)$$ ...

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