Collection of my solutions and analysis for problems on leetcode
| # | Title | Solution | Time | Space | Tag | One-Liner |
|---|---|---|---|---|---|---|
| 23 | Merge k Sorted Lists | C++ | O() | O() | N/A | |
| 32 | Longest Valid Parentheses | C++ | O() | O() | N/A | |
| 37 | Sudoku Solver | C++ | O() | O() | N/A | |
| 41 | First Missing Positive | C++ | O() | O() | N/A | |
| 51 | N-Queens | C++ | O() | O() | N/A | |
| 52 | N-Queens II | C++ | O() | O() | N/A | |
| 72 | Edit Distance | C++ | O(n^2) | O(n^2) | DP | Plain implementation of Edit Distance! |
| 76 | Minimum Window Substring | C++ | O() | O() | N/A | |
| 84 | Largest Rectangle in Histogram | C++ | O(n) | O(n) | Monotonic Stack | |
| 85 | Maximal Rectangle | C++ | O(n^2) | O(n) | Monotonic Stack | Can we convert the problem to "Largest Rectangle in Histogram"? |
| 124 | Binary Tree Maximum Path Sum | C++ | O() | O() | N/A | |
| 126 | Word Ladder II | C++ | O() | O() | N/A | |
| 127 | Word Ladder | C++ | O() | O() | N/A | |
| 140 | Word Break II | C++ | O() | O() | N/A | |
| 154 | Find Minimum in Rotated Sorted Array II | C++ | O() | O() | N/A | |
| 174 | Dungeon Game | C++ | O() | O() | N/A | |
| 212 | Word Search II | C++ | O() | O() | N/A | |
| 224 | Basic Calculator | C++ | O() | O() | N/A | |
| 315 | Count of Smaller Numbers After Self | C++ | O() | O() | Segment Tree, Ordered Set | If you like to go with segment-tree, on which array you want to make the range queries? |
| 329 | Longest Increasing Path in a Matrix | C++ | O() | O() | N/A | |
| 332 | Reconstruct Itinerary | C++ | O() | O() | N/A | |
| 352 | Data Stream as Disjoint Intervals | C++ | O() | O() | N/A | |
| 381 | Insert Delete GetRandom O(1) - Duplicates allowed | C++ | O() | O() | N/A | |
| 675 | Cut Off Trees for Golf Event | C++ | O() | O() | BFS | Just make sure you read the line "1 represents an empty cell that can be walked through." carefully! |
| 765 | Couples Holding Hands | C++ | O() | O() | N/A | |
| 773 | Sliding Puzzle | C++ | O() | O() | N/A | |
| 827 | Making A Large Island | C++ | O() | O() | N/A | |
| 834 | Sum of Distances in Tree | C++ | O() | O() | N/A | |
| 839 | Similar String Groups | C++ | O() | O() | N/A | |
| 850 | Rectangle Area II | C++ | O() | O() | N/A | |
| 882 | Reachable Nodes In Subdivided Graph | C++ | O() | O() | N/A | |
| 895 | Maximum Frequency Stack | C++ | O() | O() | N/A | |
| 924 | Minimize Malware Spread | C++ | O() | O() | N/A | |
| 952 | Largest Component Size by Common Factor | C++ | O() | O() | Union Find | |
| 968 | Binary Tree Cameras | C++ | O() | O() | Greedy/DP | When a node must have covered by a camera? |
| 980 | Unique Paths III | C++ | O() | O() | N/A | |
| 987 | Vertical Order Traversal of a Binary Tree | C++ | O() | O() | N/A | |
| 992 | Subarrays with K Different Integers | C++ | O() | O() | N/A | |
| 1032 | Stream of Characters | C++ | O() | O() | N/A | |
| 1044 | Longest Duplicate Substring | C++ | O(n * log(n)) | O(??) | Rolling Hash/String Matching | If we know a size of duplicate string, how can we confirm that? |
| 1074 | Number of Submatrices That Sum to Target | C++ | O(n^3) | O(n) | Prefix Sum | Can we convert it to a "1-d sub-array sum equal to k" problem? |
| 1192 | Critical Connections in a Network | C++ | O() | O() | N/A | |
| 1203 | Sort Items by Groups Respecting Dependencies | C++ | O() | O() | N/A | |
| 1223 | Dice Roll Simulation | C++ | O() | O() | N/A | |
| 1293 | Shortest Path in a Grid with Obstacles Elimination | C++ | O() | O() | N/A | |
| 1345 | Jump Game IV | C++ | O(n) | O(n) | BFS/Bidirectional BFS | Can you omit the recurring insertion of nodes in the queue? |
| 1463 | Cherry Pickup II | C++ | O() | O() | N/A | |
| 1473 | Paint House III | C++ | O() | O() | N/A | |
| 1483 | Kth Ancestor of a Tree Node | C++ | O() | O() | N/A | |
| 1489 | Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree | C++ | O() | O() | N/A | |
| 1494 | Parallel Courses II | C++ | O() | O() | N/A | |
| 1510 | Stone Game IV | C++ | O() | O() | N/A | |
| 1526 | Minimum Number of Increments on Subarrays to Form a Target Array | C++ | O() | O() | N/A | |
| 1537 | Get the Maximum Score | C++ | O() | O() | N/A | |
| 1553 | Minimum Number of Days to Eat N Oranges | C++ | O() | O() | N/A | |
| 1575 | Count All Possible Routes | C++ | O() | O() | DP | |
| 1579 | Remove Max Number of Edges to Keep Graph Fully Traversable | C++ | O() | O() | N/A | |
| 1617 | Count Subtrees With Max Distance Between Cities | C++ | O() | O() | N/A | |
| 1627 | Graph Connectivity With Threshold | C++ | O() | O() | N/A | |
| 1649 | Create Sorted Array through Instructions | C++ | O() | O() | N/A | |
| 1655 | Distribute Repeating Integers | C++ | O() | O() | N/A | |
| 1675 | Minimize Deviation in Array | C++ | O() | O() | N/A | |
| 1697 | Checking Existence of Edge Length Limited Paths | C++ | O() | O() | N/A | |
| 1723 | Find Minimum Time to Finish All Jobs | C++ | O() | O() | N/A | |
| 1793 | Maximum Score of a Good Subarray | C++ | O(n) | O(n) | Monotonic Stack | Can we convert the problem to "Largest Rectangle in Histogram"? |
| 2076 | Process Restricted Friend Requests | C++ | O() | O() | Union Find | |
| 2141 | Maximum Running Time of N Computers | C++ | O(n * log(n)) | O(1) | Binary Search | |
| 2147 | Number of Ways to Divide a Long Corridor | C++ | O(n) | O(n) | Ad-hoc | Calculate gaps in every two-seat segments |
| 2151 | Maximum Good People Based on Statements | C++ | O(2^n) | O(n) | Graph Traversal | If we know an assignment of goodness/badness of each vertices, can we validate that? |
| 2301 | Match Substring After Replacement | C++ | O(n*m) | O(const.) | String Matching | Mapping keys are not unique. |
| 2302 | Count Subarrays With Score Less Than K | C++ | O(n) | O(const.) | Sliding Window | Sub-array sum with limit, what else it could be other than "sliding window"? |
| 2306 | Naming a Company | C++ | N/A | N/A | N/A | N/A |
| 2312 | Selling Pieces of Wood | C++ | N/A | N/A | DP | N/A |
| 2318 | Number of Distinct Roll Sequences | C++ | N/A | N/A | DP | N/A |
| 2328 | Number of Increasing Paths in a Grid | C++ | N/A | N/A | DP | Think about if you start your traversal from each of the array positions, how you can calculate the strictly increasing paths? |
| 2354 | Number of Excellent Pairs | C++ | N/A | N/A | Two-pointers | Can you make relation between num_bit(A & B) + num_bit(A | B) with num_bit(A) and num_bit(B)? |