September Problem Solving
https://leetcode.com/problems/range-sum-query-immutable/description/
Easy sum problem. But for multiple passes, the best way is to have prefix sum array. so that we can do (right + 1) - (left) in one shot.
https://leetcode.com/problems/increasing-triplet-subsequence/
Medium problem. I went with recursion and backtracking. But the optimal solution for this is a greedy approach with single pass. we track first and second values pair. mathematical invariant. first is always the lowest value of the timeline. second is always the second lowest value of the timeline current or past based on the swap. When we encounter value greater than 3 we are at the solution. Read about greedy - local optimum global optimum when it could fail with hill analogy and coin change problem. how dp fits etc.
https://leetcode.com/problems/jump-game/
Medium problem. I tried with cache and all. But O(N) approach with the help of gemini was an elegant and efficient solution.
https://leetcode.com/problems/longest-common-prefix/
Easy problem. Min string. Index matching approach. Worked well. Another approach can use startswith but this seems good for my try.
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Easy problem. Track the prices and day variables correctly. It will smoother.
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
Another easy problem. Took couple of approaches. Lesson learned: try to cut the input space.
https://leetcode.com/problems/pascals-triangle/
Another easy category problem. Track prev row values and slide 2 values at a time find the some to create a new row. We can also take the approach of finding the current row using prev row.
https://leetcode.com/problems/longest-continuous-increasing-subsequence/
This is an easy problem. Solved it in 1 pass.
https://leetcode.com/problems/palindromic-substrings/
I have solved this with brute force - find all substrings and check whether it is a palindrome
Further I have tried to optimize this with DP - storing substrings
Then found out I can store more efficiently - instead of storing substrings I can store the indices of the substrings
Found another approach expand from center for better memory complexity