leetcode.md

To do

• https://leetcode.com/problems/longest-common-subsequence/discuss/349346/LC1143-Classic-DP-Longest-Common-Subsequence-With-Follow-up-Problems

• https://leetcode.com/problems/target-sum/

• Largest Sum of Averages https://leetcode.com/problems/largest-sum-of-averages/

• The maximum-subarray problem: 68

• Dynamic programming: https://leetcode.com/explore/interview/card/top-interview-questions-hard/121/dynamic-programming/862/discuss/151887/Classic-DP-Python-beats-97

• practice trie https://leetcode.com/problems/word-search-ii/ https://leetcode.com/problems/distinct-subsequences/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ https://leetcode.com/problems/word-break-ii/

Notes

• Quick selection uses an pointer to hold seperation/first-last element
• Reverse linked list: initialize prev as None, cur as head and use a temp inside the loop
• list comprehension 2D [head[i] + tail[j] for i in range(len(head)) for j in range(len(tail))]
• if else in list comprehension: [something if t != "" else another for t in some_list]
• For intervals or ranges, sorting by the lefts/low is usually a good start
• For Binary Tree or BST, recursion is a common choice
• Binary search or bisect left: mid = (l + r) // 2; nums[mid] < target: l = mid + 1
• Python replace comparator for sort function: from functools import cmp_to_key; res = sorted(nums, key=cmp_to_key(cmp_digit_str))
• When using heap, it will compare 2 tuple from left to right if there are equal elements. Sometimes it is a good idea to use a counter put in those tuples so they are never be the same or equal to each other
• subset: wheather existing or non-existing --> 2^n, permutation: used or not used yet --> n! or nCk
• find kth element in unsorted arr: sort, heap, quick selection
• Sometimes we need to consider between 2 or more parameters of a problem in order select different ways to sovle it and thus reducing time/space complexity respectively. For example, problem has 2 parameters m and n. If m is small, use method A to solve the problem --> O(m^2 * n). Otherwise, n is small, use method B to solve the problem --> O(n^2 * m).
• Dynamic programming: There are many ways to define a subproblem
  • Going forward by adding one by one to so dp[n] = dp[n-1] + something or dp[n] = max/min dp[i] + something; for i=0:n
  • Select an index i=0:n that split the problem into 2 sub-problem. And element at index i to be the first one processed
  • Reverse thinking, select an index i and element at this index to be the last one being processed. Then we have 2 sections on left and right which are new sub-problem. Great example: https://leetcode.com/problems/burst-balloons/description/
  • Number of subsets that sum of it is p:

    dp = [0]*(p+1)
    dp[0] = 1
    for n in nums:
    
        for i in range(p,n-1,-1):
            dp[i] += dp[i-n]
    return dp[p]

• Back track approach:

  • General back track approach for solving permutation, subset, sum, palindrome: https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

• Monotouous stack: https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step

• gcd (greatest common divisor) and lcm (least common multiple) of (A, B) (a, b) = (A, B) while b > 0: (a, b) = (b, a % b) then, gcd = a and lcm = A * B / a

• Bitmap can represent a number/word by the set it belongs to

• ziczac search/compare comes from here https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/