A List of Interesting LeetCode Problems

作者 Leon Dong 日期 2024-01-15
competitive programming
A List of Interesting LeetCode Problems

This post contains a list of LeetCode problems that I found interesting during my time practicing Data Structures and Algorithms (DSA) questions and learning competitive programming knowledge. I have been continuously practicing LeetCode questions since April 2022, this list summaried my personal experience in learning the competitive programming. I will keep updating this list, and it also serves as a useful memo for me to look back on some key knowledge related to each question.

The first version of this list is build on 12-26-2023. The date of this post shows the time of last update.

The content of this post is better to be viewed along with the search function in your browser (keyboard shortcut ctrl+f or f3)!

Patterns and Experiences

  • For questions that ask us to answer multiple queries for a fixed input and return the answer of all queries, monotonicity usually plays an important role in it. In other words, we should process the queries in certain order and keep a part of input information to make decisions on the fly.
  • If a question asks for the minimum number of steps for applying some operations to reach a certain final state, we can usually apply the reversal thinking if the operations are all invertible. In order words, we think how can we start from final state to reach the original input state.
  • If the answer to certain question is just an integer, and there is monotonicity respect to the answer, then we can probably binary search the answer and check the answer in linear time.
  • When we are required to find the minimum of maximums OR the maximum of minimums, this is also an common case involves binary search the results.
  • In some problem involves string or integer with binary bit representation, we need to find the next input string/integer satisfy certain given condition. Instead of going through the whole input list, we can also directly construct the candidates that satisfy the constraints and then check if it is inside the input. For example, 126. Word Ladder II.
  • For questions like subset sum partition or coin changes, we need to be careful about the order of outter/inner loop variables when implement the iterative dynamic programming.
  • The pre and post order traversal of tree along with the empty nodes can uniquely identify the tree structure, however this is not true for inorder traversal.
  • Linked list reverse and two point method can be very useful when you want to perform some operations on linked list with constant space complexity.
  • Add an additional dummy node in linked list realted problem can be useful.

Tricks

  • During the binary search, if you shrink left/right, you should calculate mid towards left/right, In the case you need to calculate mid toward right, use mid = (l+r+1) // 2.
  • The ceil/floor of an integer division x/y can be rewrite in the following way: (x+y-1)//y and x//y.
  • Python @cache decorator make the implementation of top-down dynamic programming much easier. However, we need to be careful about input arguments, make sure there is no redundant argument and all of them is hash compatible. In addition, call func.clear_cache() at the end to avoid memory limitation exceed error on LeetCode.
  • Trie can be useful for bit XOR related problems. For example, we can find a $y$ in Trie that maximize $y \oplus x$ (e.g. 2935. Maximum Strong Pair XOR II). In addition, we can count the number of elements satisfy $y \oplus x \le v$ (see 1803. Count Pairs With XOR in a Range).
  • Scanline algorithm do not need full size array to be allocated, we can also use a dictionary for implementation.

List of Problems