Good Morning 😻

Random posts, some of my own notes, leetcode solutions & inspirations. Hope this site lasts…

1498 Number of Subsequences That Satisfy the Given Sum Condition

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....

May 6, 2023 · mimimi

1697 Checking Existence of Edge Length Limited Paths

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....

April 29, 2023 · mimimi

1312 Minimum Insertion Steps to Make a String Palindrome

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....

April 22, 2023 · mimimi

516 Longest Palindromic Subsequence

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....

April 22, 2023 · mimimi

450 Delete Node in a Bst

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?...

April 21, 2023 · mimimi

1639 Number of Ways to Form a Target String Given a Dictionary

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))....

April 18, 2023 · mimimi

632 Smallest Range Covering Elements From K Lists

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....

April 15, 2023 · mimimi

2402 Meeting Rooms Iii

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....

April 12, 2023 · mimimi

133 Clone Graph

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....

April 8, 2023 · mimimi

AWS CloudWatch Agent Installation and Configuration

Purpose Setup CloudWatch agent on a Linux box to collect application log so that we can query the logs in CloudWatch web console or cli. Steps The official doc is long and tedious as usual, so let me note down my simple steps to setup CloudWatch agent to collect logs. Download and install the agent 1 2 wget https://s3.amazonaws.com/amazoncloudwatch-agent/ubuntu/amd64/latest/amazon-cloudwatch-agent.deb sudo dpkg -i -E ./amazon-cloudwatch-agent.deb This will install the agent to /opt/aws/amazon-cloudwatch-agent/bin...

April 6, 2023 · mimimi

Links

Mestrace - blog from my genious friend