leetcode_python

This is a repo that I showcase my capabity in Python Programming with Leetcode/ HackerRank problem(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 optimal solution is to choose between including the last K elements only or include the optimal solution of K distance prior. For example, choosing the last 4 elements or the last 8 elements. The optimal solution of K distance prior is not always taking another 4 elements. We made the same decision then just like now. We include the optimal solution of K distance prior only if that's a positive 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??

• Combination Sum: the combination of array elements is added up to reach the target. It become a matter of using the value of the current index or not since an array element can be repeated. If yes, add to curr_sum, append to sol and backtrack with the index. If not, advance the index. The baseline of completion is the curr_sum == target. The baseline of the stop is the index reach the limit or the curr_sum exceeds the target. HackerRanks's Find indexes of combination with values sum up to the target is similar but return indexes instead.

• Longest Common Subsequence: It's easier to understand the top-down memorize approach: increment the length if characters at the current indexes of both sources match and advance both indexes or advance one of indexes to see how far they can go and choose the maximum. This requires memoroization ex. using @cache to get the best time complxity of m * n. Follow the same logic to craft the bottom up DP solution which perform better. HackerRank's The common child is the same problem.

• Count Connected Components . Connected components means there are undirected links among them to form a group. Union Find (Disjoints Set) seems to be a cleaner solution than the VISITED approach using DFS or BFS. Traverse bidirectionally seems to be messy. Maintain groups of members by group indexes and have vertex mapped to its group indexes. Always keep them in sync. Don't forget to include isolated components which have no link to any other one. Leetcode's Count the Number of Completed Component has stricter criteria. Vertices of Complete Components need to link to each other (There are totally n * (n -1) // 2 links/edges)

• Next greater element with Position Offset is the same problem as Leetcode's Daily temperatures. Maintain an monotonic stack of ever decreasing element. Process smaller numbers continuously if ever encounter a greater element later.

• Generate Valid Angles Bracket. Find what angle brackets are available given prior bracket sequences based upon reasonable rules. Then process one by one in a backtrack manner. The baseline of completion is len(sol) == n * 2. General rules (taking both '<' and '>') are applied except when '<' reach the limit n or both numbers of '<' and '>' are the same. Generate Valid Parentheses.

• Height of BST need to understand how BST data are organized to have the intuition. Node values are in preorder (parent, its left child and its right child). In values of [4, 2, 6, 1, 3, 5, 7]], 4 (the root) is at index 0 and its left child(=2) is at the index 0 of leftChild and its right child(=6) at at the index 0 of leftChild. -1 represents no child. 1, 3, 5, 7 all have their children of -1 value. They are leaves. Their heights = max(height of leftChild=0, height of right child=0) + 1. We recursively build from bottom up.

• Minimum Spanning Tree with one free edge Spanning Tree is very similar to Djikstra shortestpath algorithm. Tha latter calculate the minmum time to traverse from a designated node to any node, which is max(node 0 to node 1,2,3, 4,5..n). What matter is the total time from node 0 to any node. Spanning tree can traverse from any node. What matter is the total distance or weights to visit all node. Maintain min_heap for key metrix or weight to the index and maintain min_times or min_weights for node lookup (not to re-visit the same node with a bigger time again). Return max(node 0 to node 1,2,3, 4,5..n) for the shortest path and sum(weights or distances of all linkes/ edges)

• Unique Path it is a classical Combination issue in Math. For a matrix of 7 * 3, we need to go down 2 steps/ cells and go right 6 steps/ cells. It's a matter of choosing which two borders to go down, the rest of 6 borders will have to go right. It's the combination of choosing 2 from 8. Using DP, cell (1, 1) can only come from the cell above it or the cell left to it. Sum up these twos. Pay attention to how we derive the top row and the leftmost column.

• Sherlock Anagrams: given a string, find the number of pairs of substrings of the string that are anagrams of each other. To group anagrams, we typically create a shared key of an anagrams with re-combining sorted characters. If an anagram has two variations, there are 2 pairs. If an anagram has 3 variation, it has 3 pairs (3 * 2 // 2)

• Task Scheduler with one machine and cooldown period: Since there has to be a gap (cooling period) of at least n intervals between two tasks with the same label, we use Greedy approach. Sort labeled tasks by task counts. Choose labeled task with most count using max_heap (Artificially use negative number max(5, 3, 2) = 5, min (-5, -3, -2) = -5). + 1 to reduce a negative count. Maintain a deque of (cnt, when is available). The availbale time should be the current time + the cooling gap. Push any element with the available time = the current time. Process until no more item in max_heap and deque.

• Maximum Subarray Sum Modulo: given an element array of integers a, and an integer m determine the maximum value of the sum of any of its subarrays modulo. I got this tricky solution from the discussion. Get the prefix_sum. Sort the prefix_sum. Use maximum of the prefix_sum as the default. That cover any subarray from the very beginning. Then zip two arrays with 1-off index. The idea is to find any subarray not starting from the beginning that has small negative module discrpancy. For example, prefix sum of modulo: (1,4) represent a[0:5]: (3 3 9 9 5) and [0:1]: (3), then [1:5] (3 9 9 5) will be (2 - 4 + 7)% 7 = 5. Compare and find the maximum.

• Zero-Sum Triplets within Sliding Window: cut window of the maximum size of windowSize from the original array. A window is a 0-based array and sort the window and implement threesum solution in each window. Any triplets in a window are sorted. Append triplets to 'set' to de-duplicate. However, list is not hashable and cannot be used as a key in a set. We need to implement triplets using tuple then convert them in the result. That's the trick.

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