The purpose of this checklist is to reflect on the mistakes i did while solving the problem even after solving it once or twice of many times. I will sub devide this section into TWO parts, the first part is a MUST revise and second part is to moving the first part questions there once i could solve it without any hints after few days or weeks to reflect i have made the progress.
| PROBLEM | What Went Wrong |
|---|---|
| word ladder | do pattern matching on wordList, then do pattern matching on beginWord with in BFS level order, use SET() for prevent checking the same node. Time: O(M^2 * N) where M is length of each word in the inputList and N is number of words in inputList. Space: O(M^2 * N) where we will have to store all N word combinations by doing M^2 combination. Keep in mind BFS and Visited set will cost O(M*N) |
| course schedule II | - first build map with empty array for all course then add pre-req in second loop. Apply dfs with two Set's visited and hasCycle. Lastly, make sure to loop on all courses and call dfs. Time: O(N+E) where N is the number of courses and E is the pre-reqs of each course.Space: O(N+E) at worst case from DFS callstack. |
| course schedule | - first build map with empty array for all course and then add pre-reqs which is O(N+E) time & space. Make sure check for empty array [] for no prereqs and do postorder way to add course to result, then delete from visit set, empty the course in map (i.e map[course] = []) |
| course schedule order | - same as above for building map but we will use 'TOPOSORT'. We will use visited and hasCycle set, delete course from hasCycle after processing all course children |
| count complete tree node | can be done in O(log N*log N) time with binary search. Keep in mind if the tree is complete we can calculate size by Math.pow(2, leftHeight)-1. Also here main function should return 1+ mainFunction(root.left) + mainFunction(root.right) not left(root) and right(root) |
| copy random linkedList | Need Map which will hold old node to new node, then use map data to connect. |
| longest increasing path | DFS needs be called with some minimal parent value and in recursion we check if the current cell value is greater than parent value. Also DFS in all 4 directions needs to calculate maxPath like mathPath = Math.max(maxPath, dfs(row-1, col, matrix, parentValue, memo)). Adding memo we can reduce the complexity to m*n. |
| walls and gate | BFS as we need to find distance form the GATE to it's immediate empty rooms. Check for gate then push it to Queue. Check boundry condition then push new row,col to queue & also update the cell with distance |
| decode string | Keep stack and for loop to traverse the each char, need to push to stack as long as char is not closing bracket (i.e ] ). Once we have closing bracket while loop to pop stack element as long as its not open bracket (i.e ] example: stack[stack.length-1] !== ']') and add it to new string. Then seperately pop ']' and do the same for number. parseInt the newly build number to add those many times to result array. At the end join the result array. |
| next problem | comment |
| next problem | comment |
| next problem | comment |
| next problem | comment |
| next problem | comment |
| PROBLEM | What Went Wrong |
|---|---|
| 1249. Minimum Remove to Make Valid Parentheses | Use stack to add index of '(' position, pop stack when we see ')'. if stack is not empty pop the index and remove the char corresponding to popped index from string (i.e str[index] = '') |
| 20. Valid Parentheses | Use stack whenever we see 'open brace' we push it to stack, when we see matching brace we pop. Before popping check if opping element is actually matching closing brace otherwise return false. Repeat this to all kind of braces |
| 3.Longest Substring Without Repeating Characters | Use left and right pointers with visited set. loop though the string and if we found char in visited we remove char from visited set and increment left. Do Math.max on visited set and return max at end |
| 5.Longest Palindromic Substring | two pointers left and right starts from i=0. Two while loops one for even size and one for odd size |
| 394. Decode String | Use stack, add char to stack until ']', process char from stack until we find ']', then pop the ']' and process num by using parseInt(char) >= 0. Then repeat num times and push it to stack |
| next problem | comment |
In this section i would also like to highlight the CONFIDENCE by rating the problem from 3 to 1 where 3 being the WORST and 1 is the BEST.
Rating: 3-Worst, 1-Best
| PROBLEM | Confidence Rating | Complexity |
|---|---|---|
| longest substring | 2 | time: O(N) from whileloop. space: O(min(m,k)) as we delete left char when match found |
| next problem | rating | --- |
| next problem | rating | --- |