Writing
-
Leetcode: Top k frequent elements
Continue readingGiven a list
numsand a positive integerk, return the topkfrequent items from the list. A time complexity constraint is not given for this task. -
Leetcode: Find peak element
Continue readingGiven an array
nof integers, find one peak inO(log*n)time. A peak is defined as a number where the two numbers immediately left and right are strictly less than the number. Numbers outside of the bounds of this array are considered to be smaller. -
Leetcode: Minimum Stack
Continue readingCreate a stack implementation that is able to return the minimum element as well as
pushandpopelements, all in constant timeO(1). -
Leetcode: Populate next pointers in tree
Continue readingGiven a perfect binary search tree, connect all the nodes to the node on their right
The solution is to do breadth-first-search in an iterative fashion. This puts all the nodes at the same level in a queue. By iterating over the queue we can connect each node to its successor. During this process we add the children of each node as the next entry. We repeat this process until the queue is empty.
-
Leetcode: Generate parentheses
Continue readingGiven a strictly positive integer
n, write a function that returns all possible combinations of well-formed parentheses.Parentheses can be nested and added one after the other. It is important that we don’t create invalid combinations, such as
)(. The idea then becomes to start with a single set of parentheses(). We can add another set of parentheses at three possible places:1(2)3. When looking closely, we see that1and3are the same position.We can then utilize Pythons string splitting capabilities which allow us to insert one or more characters at any place in the string. We do this by iterating over the string and inserting
()at every possible position. This creates all valid pairs like(())and()()etc.To avoid the aforementioned duplicates we can add a memory to the function and store all the visited possible combinations. This allows us to speed the process up significantly. For example when we visit
()(), we don’t need to visit it again to form()()()or()(())(forn=3) because they would already been visited.