The solution for "Educative.io/Grokking the Coding Interview: Patterns for Coding Questions" and their related Leetcode solutions
- The number ID correspond to the leetcode id
Study use only contact: Xiaoyang.rebecca.li@gmail.com
- Maximum Sum Subarray of Size K (easy)
- Smallest Subarray with a given sum (easy)
- Longest Substring with K Distinct Characters (medium)
- Longest Subarray with Ones after Replacement (hard)
- Longest Substring with Same Letters after Replacement (hard).py
- No-repeat Substring (hard).py
## Time O(N*logN) ( O(N*logN) for sorting +O(N) for merging )
## Space O(w), where ‘W’ is the maximum number of nodes on any level.
ls =[root] # queue: storage the node in breadth first order
while len(ls) > 0:
level_width = len(ls) # the width of the current level
for i in range(level_width):
n = ls.pop(0) # pop
ls.append( n.left ) # push left
ls.append( n.right ) # push right
** Breath level caluclation
-
[]
## Time O(N) Space O (H),
(H)egiht of the tree, (N)umber of nodes
- Binary Tree Path Sum (easy)
- [All Paths for a Sum (medium)]
- Sum of Path Numbers (medium)
- Count Paths for a Sum (medium)
## Time O(2^N) Space O (^N)
0 [] e.g GivenSet[1,5,3]
copy add 1
1 [] | [1]
Copy add 5
2 [][1] | [5] [1,5]
copy add 3
3 [][1][5][1,5] | [3][1,3][5,3][1,5,3]
- Subset
- Subsets With Duplicates (easy)
- Permutations (medium)
- String Permutations by changing case (medium)
- Balanced Parentheses (hard)
## Time O(logN) Space O (1)
while l <=r: # l ,r = 0, n-1
m = (l+r)//2
if too small: r = m -1
elif too big: l = m +1
## Time O(logK) Space O ()
Get largest k -> minheap, in ascending order
Get smallest k -> maxheap, in decending order