This is a repo that I showcase my capabity in Python Programming with Leetcode problems (also serves as self-studying guide with my notes). It covers all major DSA patterns. The followings are highlights:

• Number of Islands: a problem using 'Graph General' algorithm of DSF (Depth First Search) or BSF (Breath First Search). I have solutions for both. The key point is that it clears the surrounding neighers either by by setting the cell to '0' (DSF) or by adding its position turple to visited set (BFS) every time it increment number of islands. It's like clustering. Therefore, we won't over-count. The differences: DFS recursively call layer by layer and BFS make use of queue, pop and process elements while push its neighbors into queue along the way so that all elements of one layer would be processed before ones of the next layer.

• Construct Binary Tree from Preorder and Inorder Traversal: it is very high level but intuitive after watching Construct Binary Tree from Preorder and Inorder Traversal of Neetcode Video

• Longest Substring Without Repeating Characters: the 'Sliding Window' algorithm using the left pointer to shrink when encountering a repeated character checked against set of characters included.

• Trapping Rain Water: the key point is that it will trap water only if the current height is low than its surrounding ones. The amount trapped at any point i is 'min(max_l, max_r) - height[i]'.

• Rotate Image: a problem using 'Matrix' algorithm. I use 'keep' and 'restore' (variables) pattern to ensure using as little memory as possible (beating 100% runtime and 98.93% memory)

• Longest Consecutive Sequence: make use of 'set' to locate at O(1) time of the starting sequence and the following contiguous sequences, Two Sum: use map to locate its compliment number, Group Anagrams: group all anagrams with the common key in hashmap. Ransom Note: having Counters for magazine words and ransom words and make sure that ransom Counter is subset of magazine Counter

• 3Sum and Container With Most Water: problems using 'Two Pointers' algorithm. 3Sum has a lot of delicate points. Numbers need be sorted so that the current sum can compare with 0 to move the left and right pointer accordingly. Need to advance pointer(s) when encountering the same number contiguously to avoid adding duplicate pairs etc.

• Roman to Integer and Integer to Roman: interesting problems using 'Array/ String'

• Linked List Cycle: Use Floyd's Cycle-Finding Algorithm: a fast pointer and a slow pointer. It is much faster than 'out of box' implementation.

• Add Two Numbers: Use 'val' double duty to sum up carrier, l1.val and l2.val and also as the carrier for the next round. Make sure to record the last carrier even if both l1 and l2 are exhausted.

• LRU Cache: Design a Least Recently Used (LRU) cache. The solution 1 is using double linked list nodes backing LRU cache and add left and right dummy nodes to point to the least used node and the most recently used node. That is the common implmentation. The solution 2 is using 'OrderedDict[int, int]' directly. OrderedDict's move_to_end(key) and popitem(last=False) functions fit well here. Also found an interesting bug: should we compare the cap and remove key first or should we insert first then compare with the cap and remove if necessary. The latter is optimal considering insertion can be a replacement. The former can remove keys prematurely in that case.

• Reverse Linked List and Reverse Linked List II: Follow 3-step reverse process. The reverse linked list II do need to fast forward to the left position then reverse (right-left+1) time then adjust point. It's 3-stage process.

• Remove Nth Node From End of List and Rotate List: I group them together because both require the left and right pointers. The left point is at the position left to the target node or the last node after the rotation. Need to use the left and/ or the right to re-assign pointer. Also the head is subject to change. Therefore, using dummy node to code around edge cases. It's possible to rotate more than the length of list nodes. I get the remainder to avoid NullPointer issue.

• Reverse Nodes in k-Group: It is considered the toughest one in linked list group because

  1. Cannot and should not reverse the residual list which is shorter than k. The residual partial list need to be handled differently.
  2. Reverse multiple k-group. That requires save and reset lp (the last node of the previous k-group or the dummy node)

• Minimum Distance Between Three Equal Elements II: I stumbled at this one because I like to use Counter to filter. A straight forward appending to dict or defaultdict will work well. Make sure to calculate the distance along the way to save loops

• Binary search: There are variations. I stick to the while l <= r, l = mid + 1 and r = mid - 1 most of time. Tag along some processing as needed. 'Binary Search Template', Search in a Sorted Array of Unknown Size and Time Based Key-Value Store all use this approach.

• Binary search in rotate array: Rotate array is characterized by one section of ever incremental array (rotate n times for an array of n elements, I call it fully rotated array) or two sections of ever incremental array. For two sections of ever incremental array like '[4, 5, 6, 7, 0, 1, 2]', elements in the left section are always >= nums[l] (the leftmost) and elements in the right section always < nums[l]. Find Minimum in Rotated Sorted Array and Search in Rotated Sorted Array are based upon those assumptions. I detailed the logics in the code.

• Find K Closest Elements: the solution 2 is the fastest. However, it is not easy to come up with that intuition. I will go by the solution 1 of 'Find K Closest Elements' - my own implementation. This solution also helps me fully understand what scenarios can be found in a binary search: we found the target as mid or we cannot find the target (l and r flip, 'i.e' r < l). If the target is in the range, l and r will point to closes elements. If the target is out of range to the left, (Most likely lp = -1, rp = 0), we will select the leftmost K elements and vice versa.

• Course Schedule and Course Schedule II (typical DFS problems): using states: UNVISIT, VISITING, VISITED to detect graph cycle and bypass node visited before is a gracefull solution. A node pointed by its descendant nodes as a child node is a cycled node. A cycled node would NOT turn into VISITED because all its descendant nodes are not fully visited yet.

• Backtracking: I treat Letter Combinations of a Phone Number more as a DFS. It solves one kind of problem that I always want to solve: combine data from unknown number of layers which cause 'for loop' solution not applicable here. A simple DSF flow: push, recursively calling DFS and pop plus a closing process: concatenate when finish processing all layers of data will do the trick. Word Search is truely a 'backtrack' problem. I explained a scenario that a solution cannot be made if the 'backtrack' step is not implemented in my code.

• Binary Tree Level Order Traversal: this simple problem reminds me of a correct way to implment BFS

• Stack - Valid Parentheses, pairs of parentheses should always be organized in order of layers and sequences, shows stack's LIFO nature fit perfectly solving this problem. Reconstruct Itinerary is a brilliant solution combining stack and correct sorting order.

• Monotonic stack: Daily Temperatures problem will suffer O(n^2) if without a monotonic stack. The monotonic stack records those elements that haven't encounter a day of warmer temperature and they are definitively in descending order of temperature. Due to this nature, a day of warmer temperature coming in can trigger continuously pop/ process/ record efficiently until it encounter a day of high temperature in the queue.

• More Sliding Window: Fruit Into Baskets and Minimum Size Subarray Sum are problem of typical sliding window. Use the right pointer in a for loop to expand and use the left point to shrink when violating the constraint or optimizing the solution. Incrementing/ decrementing total instead of repeatly suming array data makes a big difference in large dataset.

• Network Delay Time (Djikstra's shortestpath) use Min Heap sorted in total-time to ensure nodes in shortest path will be visited first. That is combined with min_times map which not only records minimal total time to a node to prevent a node being re-visited from a longer-time path but also do the final check to ensure all nodes are visited.

• Number of Flowers in Full Bloom: make use of Min Heaps for Flower start time and end time. Sorting people in ascending order so that we can share the count and pop/ precess start and end times in time series naturally.

• DP (Dynamic Programming): DP is difficult because it is hard to detect/ define the sub-problem and is fun because the solution can be just a couple of lines of codes. I use the bottom up approach - the answer can be built bottom up from the baseline answer of sub-problems. Coin Change and Word Break are similar problem. Both require choosing options. Consider the final state as True representing finish processing and work Word Break backward. At any given index, at most one word works with segments of words so far. dp[i] represent that state at index i. dp[0] is the final state. On the contrary, there can be multiple coin combinations work so far at a given index for Coin Change. Comparison of coin count are required.

• DP (Dynamic Programming continued): I have 3 solutions for House Robber. DP array and memory O(1) from the front and memory O(1) from the back. The last solution is the most efficient (Beating 100% of runtime and 96%+ of memory) and easily explained. At given index, the maximum money robed is between forgoing robing this house but take what maximum money from the next house route going forward or robing this house and take what maximum money from two house down route going forward. For Longest Increasing Subsequence, the DP at any given index is the maximum of any prior index with its number < the number at the current index.

• Edit Distance: I always want to find the solution ever since I encounter this theory. It is easier to visualize using this link Edit Distance of Neetcode Video. Word1 is the row and word2 is the column. row len(word1) and column len(word2) are baseline data. The former represents accomplish word2 but have number of characters left for word1 to remove and the latter represents removing all charcters of word1 but have accomplished incremental characters in word2. From bottom up, any distance at the index [i][j] can be calculated by the minimum of its neighbors making corresponding moves. I have the trace for one question to illustrate moves to the solution in my code.

• Maximum Subarray Sum With Length Divisible by K: the solution combining Prefix Sum and DP. The optiomal solution is between the last K elements alone or include the optiomal solution of K distance prior. For example, choosing the last 4 elements or the last 8 elements. The optiomal solution of K distance prior is not always taking all. We made the same decision then just like now. We won't include the optiomal solution of K distance prior if that's a negative number. I think that I am thinking more in DP way now (Surprising!!)

• Count Elements With at Least K Greater Values: an efficient solution combining Counter and sorting counter key reversely to process. I single out this solution because I beated 100% runtime and 100% memory.

• Make Sum Divisible by P: this is using 'Modulo Arithmetic'. It is a new learning experience to me. If the sum of the array is a === (mod P), we need to remove a subarray with its sum of a === (mod P) too. If an index i has its sum of b === (mod P), we must find a another index 'j' that has sum of x === (mod p) so that (b - x + P) % P = a === (mod P). We can get x using Modulo Arithmetic as (b - a + P) % P. We can get j from the hashmap using x as its key. The subarray of the index between i and j is what we need to remove.

All Python modules got accepted by Leetcode and passed all tests. I added testcases for those Python modules commited initially. Will spare time to add testcases for the rest of Python modules. More are coming up... Also thanks to Neetcode YouTube videos, Greg Hogg's YouTube videos and Leetcode' Editorials. They inspired me solving a lot of tough problems or finding more efficient and graceful solutions