Leetcode

What I’ve learned from various topics.

Log Template

---

Problem # and title

Summary:
Concepts:
Initial Approach:
Mistakes:
Key Insight:

Problems

226. Invert Binary Tree

Summary: Effectively flip a binary tree along an axis, i.e. every left child is now a right a child.
Concepts: DFS (Recursive)
Mistakes: Mostly learned that it can often be easier to test the legitimacy of a node after traversing rather than before by checking the children individually. This isn’t always feasible, or even desirable, but can shorten/clean code.

def dfs(node):
	# Traverse anyway, find out node doesn't exist, get out
	if node doesnt exist:
		return
 
	# (As opposed to) Check beforehand before traversing
	if node.left exists:
		search(node.left)
	if node.right exists:
		search(node.right)

543. Diameter of Binary Tree

Summary: Find the length of the longest path between any two nodes in a tree.
Concepts: DFS (Recursive)
Initial Approach: None
Mistakes: Wasn’t able to reframe the problem into a simpler sub problem.
Key Insight: Each node has a height, indicating the length of the longest path from that node to some leaf node. We can sum the heights of the left and right child for any given node to find the longest path through that node. From there, it is as simple as finding that sum for each node and selecting the maximum.

100. Same Tree

Summary: Determine whether two trees are equivalent in structure and value.
Concepts: DFS
Initial Approach: Decided to use iterative DFS approach even though recursive would’ve been shorter. My conditions for failure were checking A) one node exists but the other does not and B) value does not match (including None).
Mistakes: I separated the fail condition into two separate conditions when they could have been just one.
Key Insight: I can skip cases where both are None (X, X). This allows me to have a single fail condition if only one exists (X, O)/(O, X) or if the values are not equivalent (O,O). In reality, this is a minor logic change, but reduces it by a single condition by combining all of the fail conditions.
Example:

My Solution	Target Solution
If (O,X) or (X, O): FAIL If (O and O != O): FAIL If (O, O): Scan children Otherwise: SKIP	If (X, X): SKIP If (X, O) or (O, X) or O != O): FAIL Otherwise: Scan Children

208. Implement Trie (Prefix Tree)

Summary: Implement a trie data structure
Concepts: Trie Data Structure
Initial Approach: Was not at all familiar with this data structure and decided to research how it works.
Key Insight: This is a great introduction to what a trie is and how it works. I ended up taking comprehensive notes about the Trie Data Structure.

141. Linked List Cycle

Summary: Given the head of a linked list, determine whether it contains a cycle.
Concepts: Floyd’s Cycle Finding Algorithm
Initial Approach: I decided to go with the “visited” set approach, returning true upon reaching a previously visited node. However, this has a space complexity of O(n).
Key Insight: There is a cycle finding algorithm known as “The Tortoise and the Hare” where you have a fast pointer and a slow pointer. The slow advances by one and the fast advances by two. If these two pointers are traversing a cycle of some sort, then the hare is bound to lap the tortoise. There is no concern of them “missing” each other, because if the hare advances by two, and the tortoise runs away by 1, the hare has closed the gap by 1 node (2 - 1 = 1).

3. Longest Substring Without Repeating Characters

Summary: Given a string, find the length of the longest continuous substring without duplicate characters.
Concepts: Sliding Window, 2 Pointers
Initial Approach: Used a sliding window approach where when the right pointer advances, we fill a “seen” set containing the unique characters of the current substring. When the left pointer advances, we remove it from the “seen” set.
Mistakes: It wasn’t entirely necessary to keep track of a r index in a while loop, I could just for r in range(len(s)) which makes a little more sense semantically.

143. Reorder List

Summary: Reorder a linked list in the following order: [0, n-1, 1, n-2, 2, n-3, ...]. In other words, alternating iterating from the head and tail towards the middle.
Concepts: Slow and fast pointer, reversing linked list
Initial Approach: I had an idea that required knowing where the middle was which I could have done if the problem supplied me with an n. I figured that if I had the midpoint, I could reverse the LinkedList from that point giving me [0, 1, 2, 6, 5, 4]. I could then just zip iterate linearly from the head and midpoint giving me [0, 6, 1, 5, 2, 4] which is the solution.
Key Insight: Really make sure you have how to reverse a linked list down, it feels like I was solving another a whole other Leetcode problem from scratch.

572. Subtree of Another Tree

Summary: Given the roots of two binary trees, determine if root contains subTree at some point.
Concepts: Tree Traversal (DFS)
Initial Approach: I overthought the problem a bit and tried to find a more efficient solution when in reality it was an extension of 100. Same Tree.
Mistakes: There was a little bit of confusion regarding if root == None in the main problem and why I need it. I would not have been able to explain it in the moment, however, it’s essentially the same as the mistake from 226. Invert Binary Tree, perhaps I should have this idea down.
Key Insight: Try to go for a naive solution at first, especially if ruminating is halting your progress.

15. 3Sum

Summary: Given an array of numbers, return indexes of all unique triplets where the numbers at those indexes sum to 0.
Problems:

1. Duplicate Combinations - We may run into cases where we have multiple combinations all with the same indexes, but in a different order.
2. Duplicate Values - We may run into cases where, even though they have different indexes, they share values the same values in either the same or different order.
   Concepts:
   Initial Approach: I was considering some sort of sliding window approach but was ultimately lost.
   Key Insight: There are two main ideas behind solving this problem/making it O(n²).

• Avoiding Duplicates: This was difficult to wrap my head around in regards to triplets, but is ultimately pretty simple when considering the smaller problem of finding unique pairs. I have explained my rationale in the note Unique Combinations.
• Sorting the List: This helps us solve problem #2 where we have duplicate values despite having different indexes. By sorting the list, which is generally O(n²) or better, we can skip values we have already checked simply by checking the previous index.
• TODO There is more to this problem, keep looking at it.

271. Encode and Decode Strings

Summary: Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
Concepts: Strings
Initial Approach: I figured we could just use a non ASCII character to delimit the strings. After all, in C a string is terminated with a NULL byte which is effectively a delimiter in that context.
Mistakes: I thought that using a delimiter of format (numChars)# was redundant and basically equivalent to using any other delimiter, meaning that strings containing, say, 4# would be decoded incorrectly.
Key Insight: By first reading a number, which indicates the length of what is to be read, and including a delimiter so we don’t read numbers from the string itself, we can ensure safe decoding regardless of input. This reminds me of how unsafe functions in C were replaced with functions that take an additional parameter, n, specifying the numbers of characters to be read/written to prevent buffer overflows.

703. Kth Largest Element in a Stream

Summary: Design a class to find the kth largest integer in a stream of values.
Concepts: Heap Data Structure
Initial Approach: I thought a max-heap of size k would fit my use case, because I could then check the last element of the heap array for the kth largest.
Mistakes: My initial approach attributes too much to the capabilities of a heap: heaps do not maintain any sort of ordering beyond the heap property, there is no guarantee that the last element of that array would be the minimum.
Key Insight: The initial approach was in the right direction. We just need to flip it to a min-heap of size k which we’ll define to store only the k largest elements we’ve seen so far—this is key—since it guarantees the root to be the kth largest. When we receive a number that is larger than the minimum, then there is no chance the minimum is the kth largest element anymore, so we need to pop it from the heap. After percolation, the root will become the kth largest again.

It’s not necessary to check if the new value is greater than the minimum, we can just push it anyway and pop() (as long as the heap size is k afterwards). Not sure if I like this solution rather than being explicit, as it results in redundant insertions.