Stage 1 · Code
Dynamic Programming
Longest Increasing Subsequence
O(n²) DP and O(n log n) patience sorting approach.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
O(n²) DP Solution
dp[i] = length of LIS ending at index i. For each i, check all j < i: if nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1). Answer = max(dp).
Golis-o(n²)-dp.go
22 linesLn 1, Col 1Go
dp[i] = 1 initially (single element). For each previous j, if nums[j] < nums[i], can extend. Time O(n²), space O(n).
O(n log n) Patience Sorting
Maintain array tails where tails[len] = smallest ending value of all increasing subsequences of length len+1. For each num, find insertion point with binary search. Length of tails = LIS length.
Golis-o(n-log-n)-with-binary-search.go
24 linesLn 1, Col 1Go
tails is always sorted. Binary search finds where to place num. If num > all tails, extend LIS. Else replace first >= num (maintains smallest possible tail). Length of tails = LIS length.
Reconstructing LIS
O(n²) DP: track parent pointers. O(n log n): track index of each element in tails, and predecessor index. Reconstruct by following parents from last element of LIS.
Golis-with-reconstruction-(o(n-log-n)).go
46 linesLn 1, Col 1Go
Track tailIndices (index in nums of each tails value) and prev pointers. Reconstruct from last tail index following prev links.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.