Leetcodes

1498. Number of Subsequences That Satisfy the Given Sum Condition I hate these array problem and subsequences… This is the daily challenge on 6 May 2023, I opened up the submission tab and found that I tried this problem 1 year ago and from the submission history, I recall how miserable it was… Idea I usually look for two ways to solve array+subsequence problem. DP Two pointers This problem has a test case size of \(10^5\), so DP is out of the game, and two pointer does seem promising....

1697. Checking Existence of Edge Length Limited Paths Idea This problem at first looks a lot like a shortest path problem, but the test case size(\(10^5\)) seems to be too big. Another observation is that the problem doesn’t really ask for shortest path, instead it asks if the max weight along the path is smaller than something, (hopefully) this relaxes the problem a little bit. As there is no easy way to find out the max path weight given two random nodes in the graph(probably just DFS and BFS, which result in \(n^2\) time complexity, Floyd-Warshall algorithm has \(n^3\)), we try something else....

1312. Minimum Insertion Steps to Make a String Palindrome This is the daily challenge on 22/Apr/2023. Idea To solve this problem, there is one key point that we can’t miss. Assume x is the length of the longest palindromic subsequence, and n is the length of s, the result is simply n-x This is because for those chars that are not in the longest palindromic subsequence, we have to add one char for each of them to make them palindromic....

516. Longest Palindromic Subsequence Idea I re-visited this problem because of another hard problem (1312), and I found that this problem deserves a post on its own. We’re trying to find the longest palindromic subsequence, there are few ways to solve subsequence problems and probably the first one we should consider is Dynamic Programming(DP). DP State We want the longest, so we start from index 0 and index len-1, and takes them if they are the same, do something else if not, so we need to keep track of two indices, left and right....

450. Delete Node in a BST Idea This brings me back to my university time when we were forced to manually implement heap…… However, this one is simpler but still, not an easy task to do. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node. The searching part is easy, let’s skip it. How do we delete a node?...

In my personal opinion, this stupid problem is harder than an ordinary DP, because: state transition is weird(multiplication…) we need another data structure to pre-compute something Idea We need to match chars in word and chars in target, but with the given restriction. once we take a char in word, the char and the char to the left from all words are not available anymore we can start from any word, not necessarily from the first word target can be shorter than words[0] Base Case Success case: chars in targets are all matched(m>=len(target))....

632. Smallest Range Covering Elements from K Lists This stupid problem… I’ve read the solution 2 months ago and failed to understand it. I know it will keep hunting me and today it comes back in another problem list… Idea In this section, don’t worry too much about how we implement this using code, just get the rough idea, in the end, the idea of how we solve it matters, the code will naturally comes out when the idea is clear....

2402. Meeting Rooms III Ideas Heap comes to my mind when I know that I need to “schedule the earliest meeting” and “use smallest room index”. The thinking process and some decisions we need to make: when there is an available room, should we just take it? yes if we haven’t started any meeting else we might have some meeting rooms that were previously occupied but now ready to be used....

133. Clone Graph My last AC submission was in May 2022, almost one year has passed and fk my memory about this problem has gone too. 🥲 My first intuition was nearly correct (DFS and clone along the way), however, I messed up with some details. Then I came up with the first approach below… Not fast but quite easy to understand. First Approach General Idea The complicated part about this problem is how do we avoid going into a loop and make sure we cover every edge in the cloned graph....

87. Scramble String Idea Reading through the description, take note of these: If the length of the string is 1, stop. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x. The above two pieces of information heavily hint that this is a DP problem. The first sentence tells us the base case, length of string is 1....