Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #300 Longest Increasing Subsequence. The problem provides an array of integers, with the expected output being the length of the longest increasing subsequence within the array.
I've done this problem before as it is an absolutely classic dynamic programming problem, but it did take me a bit to recall how exactly it is solved. The main idea is that for each number, we have to evaluate the various optimal results for the previous numbers, and pick the optimal solution for us at the current index. That optimality and choice is determined by whether the number is strictly less than our current number, and if the chain length + 1 is greater than any other chain length that we have seen so far. This results in an O(n^2) algorithm.
The follow-up was tricky. Sorting was ruled out immediately as it would not preserve the order of the sequence, and a binary tree seemed a bit strange as it would not address the problem directly. I thought (incorrectly) that the problem may have involved union-find, but ultimately discovered that the answer to the O(nlogn) approach lies within a lesser-known algorithm known as patience sort. This algorithm produces a sorted list of items, with smaller items overriding the place of larger items, with the length of that list being the length of the longest increasing subsequence.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/16 hours per week, [93/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion, coding begins
10:05 - Coding Begins (Dynamic Programming)
30:08 - Solution Discussion (Patience Sort)