Leetcode notes

You can find solutions of Leetcode problems online. Sometimes my own solutions are more intuitive to me. Here I present my solutions that I find interesting in Python3 and my notes.

In solving a problem, the very first step is to write test cases that cover the whole problem domain (aka Test-driven development). This forces you think more about the problem and understand it thoroughly.

121. Best Time to Buy and Sell Stock:

def maxProfit(self, prices: List[int]) -> int: 
    maxProfit = 0
    iLowestPrice = 0
    #runtime is O(n) because there is only one for loop
    for j in range(iLowestPrice + 1, len(prices)): 
        profit = prices[j] - prices[iLowestPrice]
        if profit > maxProfit:
            maxProfit = profit
        if prices[j] < prices[iLowestPrice]:
            iLowestPrice = j
    return maxProfit

141. Linked List Cycle: To check if a node object already exists, using a set (hash set) instead of a list is much faster, in fact 66 times faster for this particular problem. This is due to comparing the hash-based key when using a set instead of comparing all fields of objects when using a list.

104. Maximum Depth of Binary Tree: My inefficient Python solution runtime (105 ms) was 26 times slower than my similar C++ solution (4 ms). For testing purposes, I wrote a function to create a binary tree from a list:

def toBSTree(aList):
	nodes = []
	for n in aList:	
		nodes.append(TreeNode(n))
	for i in range((len(aList)-2) // 2 + 1):
		left = nodes[2*i+1]
		right = nodes[2*i+2]
		if left.val is not None: nodes[i].left = left
		if right.val is not None: nodes[i].right = right
	return nodes[0]

Breadth/Depth first search algorithms use the following data structures:

1. adjacencyList[node] = neighbor nodes of each node
2. isVisited[node] = was this node visited before

If you want to find the path between two nodes, you also need prevNodeOf[node] = the node visited before this node.

18.09.2022: Understanding stack/queue usage to traverse all nodes in a tree is fundamental.

22.09.2022: In BINARY TREE there is no ordering in terms of how the nodes are arranged. In BINARY SEARCH TREE [BST] the left subtree has elements less than the nodes element and the right subtree has elements greater than the nodes element.

24.09.2022: Priority queues, min heaps outperform array sorting when items are added to or removed from array because heap insert is O(logN).

25.09.2022: Algorithm and geometry problems are similar in that geometry problems usually require drawing auxiliary lines to more easily see the solution. Algorithm problems also require you to add scaffolding. A typical example is the meeting rooms problem where you first apply sort to simplify comparison and reduce overall complexity from O(n^2) to O(n*logn). And as with geometry, you need a lot of practice to enrich your toolbox of methods to tackle a given problem.

24.10.2022: Get bit value of a number at position i: (number >> i) & 1

06.11.2022: To prevent integer overflow in C++, instead of checking if X + Y > Z, check the equivalent statement if X > Z - Y

17.11.2022: Dynamic Programming

14.12.2022: DFS/BFS isVisited = all valid paths from a start node

22.12.2022: Stack and queue data structure provide you with an easy way to go back to a previous state and continue from there.

04.01.2023: Reason for pattern searching with finite automata being linear in text size n, O(m^3*alphabetSize + n), is that for every iteration of text, state machine does only one operation, i.e. transition to next state using current state and current character. Whenever state reaches final state, it means that pattern was found. For transition table construction by considering longest prefix==suffix, see this video.

08.02.2023: Recursive and iterative binary search tree traversal:

def printBSTreeRecursive(root):
	if root is None: return
	print(root.val)
	printBSTreeRecursive(root.left)
	printBSTreeRecursive(root.right)

def printBSTreeIterative(root):
	stack = [root]
	while stack:
		node = stack.pop()
		print(node.val)
		if node.right: stack.append(node.right)
		if node.left: stack.append(node.left)

01.03.2023: My Leetcode replit repo. Binary search tree keys have to be unique.