Hey, I am so glad to say that I have taken the next step in my competitive programming journey. I was starting from nothing about linked lists and have now started learning some of the tougher concepts. After covering all the basics, I moved on to more complicated topics. I've learned about linked lists and tackled a few related questions over the last few days. On Thursday I tried most of the questions using Dojo-related questions so that I can use some of them for my up-coming dojo this week. I prepared accordingly.
Friday ended solving all three advanced problems, which were Longest Valid Parentheses, Frog Jump, and Merge k Sorted Lists.
The first problem was Longest Valid Parentheses : given a string containing only parentheses, find the length of the longest valid substring of balanced parentheses. By using a stack to keep track of unmatched parentheses and their indices, I could compute the maximum valid length in an efficient manner.
For Frog Jump, I was to determine if a frog could cross the river by jumping between stones, where the length at each step depends on the length of the previous jump. This is a dynamic programming problem in which I had to construct a set-based state tracker for each stone and keep track of all the possible jump lengths.
Lastly, I worked on the problem of Merge k Sorted Lists. This is the classic problem where one must merge several sorted linked lists into one. Using a priority queue, I held up the smallest elements of all the lists and merged those up.
Top comments (0)