2021刷题打卡

2021/07/18

HashMap tag under FB

939. Minimum Area Rectangle

• The key is to use diagonal points to determine the other two points
• How to build hashCode() method ? Objects.hash(...);
• O(N^2) solution
  

311. Sparse Matrix Multiplication

• Wired question. No clear problem statement regarding what is matrix multiplication.
  

73. Set Matrix Zeroes

• Can be easilly resolved if no limitations on space complexity. Use a list to store the pair, so O(M+N).
• For O(1) space complexity solution, use the first row/column as marker. One note here is the data of first row/col will be poluted so we need to record do we need to set zeroes for them before marking the rest of the data. Another trick is we need to set zeroes for row 1 onwards and col 1 onwards, then get back to first row and first col.
  

380. Insert Delete GetRandom O(1)

• This question worth revisit. The key problem is how to ensure all the three operations at O(1), and the key is to use HashMap and ArrayList combined. Note to analyze how those data structures would perform on each operation.
  

325. Maximum Size Subarray Sum Equals k

• prefix sum, 鬼使神差的没做出来
  

Target for tomorrow: DFS
刷题大纲

✅  HashTable
⭕ Depth-First Search
⭕ Dynamic Programming
⭕ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum

两天没刷题的我来了。。。
2021/07/21
FB Depth-First Search Tag

Easy
426. Convert Binary Search Tree to Sorted Doubly Linked List

• So unfamiliar with DFS. The easiest way to solve this problem is use the iterative solution (stack)
• Another trick is to use a dummy node to acting as the head.
  

572. Subtree of Another Tree
112. Path Sum

Medium
1305. All Elements in Two Binary Search Trees

• Merge two BST into a sorted list: using DFS/stack, otherwise, we can do sorted merge (sub-optimal solution)
  

1382. Balance a Binary Search Tree
230. Kth Smallest Element in a BST

• O(H+K) iterative solution came out easily once get familiar with the DFS/stack solution
• Follow up: what if the BST is modified frequently? B+Tree: BST + DoublyLinkedList just like LRU cache (insert/delete relies on BST (O(logN)), search using doubly linkedList)
  

1026. Maximum Difference Between Node and Ancestor

• Initially only figured out O(N^2) solution by myself, compare every pair of node. The trick is to find the min/max from each root-to-leaf route to get O(N) solution.
  

2021/07/21
FB Depth-First Search Tag

Medium

419. Battleships in a Board

• DFS (visited[][]). The trick is to only count up-left-most nodes
  

1123. Lowest Common Ancestor of Deepest Leaves

• The same as "865. Smallest Subtree with all the Deepest Nodes"
• It's a little more complicated than normal DFS question, we need to pass multiple parameters back during DFS call.
  

2021/07/21
FB Depth-First Search Tag

Medium

339. Nested List Weight Sum

• pass in depth
  

1110. Delete Nodes And Return Forest

• Determines the criteria to add nodes to result is 1) the node is root for a tree, 2) the node is not deleted
• Another trick to solve this problem is when current node is deleted, then the children are all promoted to be the root nodes of trees.
  

695. Max Area of Island

• Easy to solve with recursion
  

515. Find Largest Value in Each Tree Row

• Use BFS instead would be super easy.
  

323. Number of Connected Components in an Undirected Graph

• A good excercise for union find [youtube link], we will revisit this later when doing exercises for union find (path compression, union by rank, etc.)
  

529. Minesweeper

• A little bit hard to understand the rules.
  

199. Binary Tree Right Side View

• BFS
  

694. Number of Distinct Islands

• How to store an island's shape? using the DFS traversal direction as the string representation. One key note here is we need to track the position we do backtracking.
  

863. All Nodes Distance K in Binary Tree

• Build a graph first, then use BFS.
  

1644. Lowest Common Ancestor of a Binary Tree II

• Not able to solve the problem using recursive solution without hint..
  

814. Binary Tree Pruning

2021/07/21
FB Depth-First Search Tag

Medium
刷得越来越慢了。。graph好难🤯
114. Flatten Binary Tree to Linked List

• create a helper method that would return the "tail" or the rightmost node from the subtrees. The key logic is to link the left-tree's tail with the right tree's head. O(N), O(N)
• To reach O(1) space complexity, we can use some trick to link the rightmost node of leftree with the right tree's root with iterative approach.
  

341. Flatten Nested List Iterator

• Stack:add/pop, Queue: offer, poll
• How to leverage Stack to solve this problem
  

449. Serialize and Deserialize BST

• This is a follow-up question to 297. Serialize and Deserialize Binary Tree, some more reading here.
• One key learning here is serialize and deserialize recursively in the same order (preorder for example), then we'll get the result.
• Another trick here is to eliminate the null nodes from the encoded string, we should leverage BST's attribtue that left child < root < right child.
  

721. Accounts Merge

• The tricky part is how to build the graph. This problem can be solved by either DFS / bfs.
• Can exercise latter with union-find.
  

Micellaneous (Contest)

• 5804. Check if All Characters Have Equal Number of Occurrences
• 5196. Number of Visible People in a Queue brute-force, not able to optimize in a way that avoid TLE.
  

2021/07/25
Weekly Contest 251
Solved:
1945. Sum of Digits of String After Convert
1946. Largest Number After Mutating Substring

• Not fully understand the question initially, thought we can mutate any character.
• Lesson leant: need to clarify the question first before start solving it.
  

Unsolved:
1947. Maximum Compatibility Score Sum

• Backtracking + DFS
  

Monotonic Stack
1944. Number of Visible People in a Queue

Graph, DFS:
827. Making A Large Island

• Two steps: 1) coloring the island, at the same time count the area for this island; 2) starting with cell value is zero, connect the island in four directions.
• 2 edge cases to consider: if the entire map is one island, if there is no island at all.
  

124. Binary Tree Maximum Path Sum

• Need to consider node.val can be negative.
  

314. Binary Tree Vertical Order Traversal

• No bug :)
  

987. Vertical Order Traversal of a Binary Tree

• Similar to the question above.
  

269. Alien Dictionary

• Topological sorting, graph, BFS
  

211. Design Add and Search Words Data Structure

• Trie + DFS
  

536. Construct Binary Tree from String

• Hard to follow... need to revisit later.
  

✅ HashTable
✅ Depth-First Search
⏹ Dynamic Programming
⭕ Union Find
⭕ Backtracking
⭕ Divide and Conquer
⭕ Breadth-First Search
⭕ Stack
⭕ Queue
⭕ Heap (Priority Queue)
⭕ Graph
⭕ Two Pointers
⭕ Prefix Sum

Target for July 26: DP

2021/07/26

FB - Dynamic Programming - Sort By Frequency
509. Fibonacci Number
53. Maximum Subarray

• This is my 3rd time trying to solve this problem. However, I am still not able to solve it with minimal efforts and bug free.
• Good reading for this article about Kadane's algorithm
  

1884. Egg Drop With 2 Eggs and N Floors

• A famous DP problem that is hard to implement, worth revisit and read this article again.
  

139. Word Break

• Trie + DP
  

2021/07/27

勤奋工作的一天，只刷了一道explore题
16. 3Sum Closest