UMCPC x CISSA Hitchhikers Guide to Leetcode === ###### tags: `umcpc` --- ## Tips & Tricks 1. Team Blind bang for your buck leetcode https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-100-LeetCode-Questions-to-Save-Your-Time-OaM1orEU --- ### Tips & Tricks 2. Don't look at the solution until you have attempted (actually attempted) for at least 30mins. If you do, try to look for a discussion solution in a different language / approach and implement that. --- ### Tips & Tricks 3. If you do get stuck, google the concept and try to apply it - as soon as you see the solution code your brain checks out and you will 99% of the time not remember it --- ### Tips & Tricks 4. Solved a question, but with some help / solutions? Set a reminder to redo it in a week. Anki style repition learning --- ### Tips & Tricks 5. Don't attempt questions that make explicit mention of techniques or algorithms you don't know yet... Instead research the algorithm and then try them --- ### Tips & Tricks 6. If you have an interview coming up with G,F,A etc invest in LC premium and do the questions that are tagged with that company (pretty good odds you will get the same or similar question) --- ### Tips & Tricks 7. Try not to cram, 1 a day or 3-4 a week over several months will get you so much more than 50 in 2 weeks. --- ## Study Guide **Starting Out**: Little to no experience, cannot complete most easy's in less than 20-30 minutes. - 30-50 Easys, focus on variety, trees, dp, array, graphs --- ### Study Guide **Semi-Confident**: Can complete most easys in less than 30 minutes, solving some mediums that you are comfortable with - Review DS & Algo (geeks4geeks) - Try and do a variety of questions but focus mainly on easys in topics you aren't great at, mediums. --- ### Study Guide **Confident**: Can solve all easys in <20 mins, most mediums in <30mins - Focus on weak topics in mediums - start branching into popular hard questions that get asked frequently. Maybe think about doing some competitive programming questions? (they range from med - hard+++) --- ### Study Guide **Super Confident**: Can blitz any medium / easy, solving most hards in < 30 mins. - Come join UMCPC, leetcode is fun but there is a whole world out there of much harder and more interesting problems --- ## 543. Diameter of Binary Tree Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. --- ### 543. Diameter of Binary Tree (Easy) Example 1: ``` 1 / \ 2 3 / \ 4 5 ``` Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. --- ### Approach We know that we are going to require the max_depth of any subtree. Consider the case where we might not take the root as part of the max_diameter. --- ### Approach Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. So it is apparent that a subtree could have the maximum path - but we also need to return the depth at each stage to use in our computation. --- ### Approach In order for that to work, we then need to essentially either define two functions - one to get the depth at each node and one to compute the diameter. Or... we can combine both of these into one function returning a tuple. --- ### Solution ```python class Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: best = 0 def diam(root): if not root: return 0, 0 l, lbest = diam(root.left) r, rbest = diam(root.right) best = max(rbest, lbest, l + r) return max(l, r) + 1, best return diam(root)[1] ``` --- ## 438. Find All Anagrams in a String (Medium) Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. --- ### 438. Find All Anagrams in a String Example 1: ``` Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". ``` --- ### 438. Find All Anagrams in a String Example 2: ``` Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab". ``` --- ### Approach Brute Force? Try every starting position and iterate up to len(p) and check if anagram. Then move on. Complexity = $O(nklog(k))$ --- ```python from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: np = len(p) ns = len(s) res = [] for i in range(ns): for j in range(np): if (s[i:np].sort() == p.sort()): res.append(i) return res ``` --- ### Approach We are repeating a fair bit of work - for starters having to sort then compare them is slow. We also consider every letter k times, when really we could consider it just once. We can change our approach to instead use an unordered multiset object to compare at every iteration to remove the log factor. --- ```python from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: np = len(p) ns = len(s) cur = Counter(p) res = [] for i in range(ns): for j in range(np): if (Counter(s[i:np]) == cur: res.append(i) return res ``` --- ### Approach But we still have a consideration every k times for every letter. How about instead of adding and remove the whole sequence of k letters each time, we iterative add them and check at each step ... --- ### Solution ```python from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: np = len(p) ns = len(s) ref = Counter(p) cur = Counter() res = [] for i in range(ns): cur[s[i]] += 1 if i >= np: if cur[s[i-np]] == 1: del cur[s[i-np]] else: cur[s[i-np]] -= 1 if cur == ref: res.append(i - np + 1) return res ``` --- ## 986. Interval List Intersections (Medium) Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].) --- ### 986. Interval List Intersections Example 1:  ``` Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. ``` --- ### Approach A brute force approach would be to compare every interval against every other interval (two for loops). This would give us a $O(n^2)$ approach. I wont code this one out but i hope it is intuitive how it would work. Note that although the problem statement doesn't explicitly state so - you may assume its sorted --- ### Approach Another way we could approach this problem is to instead keep an index of our current interval we are checking for both lists. Then whenever we reach a situation where we can't match it with another interval we increment the index. This is going to be the optimal solution that runs in O(n+m) --- ### Approach  --- ### Solution ```python class Solution: def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]: ans = [] i = j = 0 while i < len(A) and j < len(B): lo = max(A[i][0], B[j][0]) hi = min(A[i][1], B[j][1]) if lo <= hi: ans.append([lo, hi]) if A[i][1] < B[j][1]: i += 1 else: j += 1 return ans ``` --- ## 42. Trapping Rain Water (Hard ... but old) Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. --- ### 42. Trapping Rain Water Example 1:  ``` Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 ``` --- ### Approach Brute force - for each element in the array we find the max(left) and max(right) take the min of that and minus the height. Intuitively this isnt too bad - obviously its going to be $O(n^2)$ time which we dont want. --- ```python class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n ==0 : return 0 ans = 0 # deal with i < 0 && i > n-1 for i in range(len(height)): max_l = max(height[i+1:]) max_r = max(height[0:i]) min_max = min(max_l, max_r) res = min_max - height[i] ans += res return ans ``` --- ### Approach It may be inefficient but we have discovered the key component to this question. The max height left and right at each index. If we can optimize this then we are well on our way. --- ### Approach Precomputation (Dynamic Programming). Perhaps we create two auxillary arrays and store the maxes left and right respectively at each index. This way the water catch calculation becomes O(1) time and we only loop once. ---  ``` heights = [0,1,0,2,1,0,1,3,2,1,2,1] L = [0,1,1,2,2,2,2,3,3,3,3,3] R = [3,3,3,3,3,3,3,3,2,2,2,1] ans = [0,0,1,0,1,2,1,0,0,1,0,0] = 6 ``` --- ### Solution ```python class Solution: def trap(self, height: List[int]) -> int: n = len(height) if n ==0 : return 0 lheight = [0 for _ in range(n)] rheight = [0 for _ in range(n)] lheight[0] = height[0] rheight[n-1] = height[n-1] for i in range(1,n): lheight[i] = max(height[i], lheight[i-1]) for i in range(n-2, -1, -1): rheight[i] = max(height[i], rheight[i+1]) ans = 0 for i in range(1, n): ans += min(lheight[i], rheight[i]) - height[i] return ans ``` ---