#300 Longest Increasing Subsequence
frequently reported atSamsungByteDance / TikTokPayPalWalmartMicrosoftAmazon
the problem
In plain words
Return the length of the longest strictly increasing subsequence of nums (elements in order, gaps allowed).
in nums = [10,9,2,5,3,7,101,18]
out 4
[2,3,7,101] (or [2,5,7,18], …).
in nums = [0,1,0,3,2,3]
out 4
in nums = [7,7,7,7,7,7,7]
out 1
- 1 ≤ nums.length ≤ 2500
- −10⁴ ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternLongest increasing subsequenceBinary search (exact & bounds)
Define dp[i] as the longest run that ENDS at i — then it's 1 + the best dp[j] for any earlier smaller nums[j]. For O(n log n), only keep the smallest possible tail for each run length.
solutions
From brute force to optimal
longest(i, prev): skip nums[i], or take it if it's bigger than nums[prev].
- State = (current index, index of last taken).
- Return max(skip, take).
Every element is taken or skipped.
Recursion depth.
class Solution { public int lengthOfLIS(int[] nums) { return longest(nums, 0, -1); } /** Longest increasing subsequence from index i, where prev is the index of the last pick (-1 = none). */ private int longest(int[] nums, int i, int prev) { if (i == nums.length) return 0; int skip = longest(nums, i + 1, prev); int take = 0; if (prev == -1 || nums[i] > nums[prev]) take = 1 + longest(nums, i + 1, i); return Math.max(skip, take); }}There are only n × (n + 1) (i, prev) pairs.
- memo[i][prev + 1] (shift so prev = −1 fits).
- Check, compute, store.
n² states × O(1).
The 2D memo (25 MB for n = 2500 — heavy).
class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[][] memo = new int[n][n + 1]; // memo[i][prev + 1]: shift prev by 1 so "none" (-1) fits at column 0 for (int[] row : memo) Arrays.fill(row, -1); return longest(nums, 0, -1, memo); } private int longest(int[] nums, int i, int prev, int[][] memo) { if (i == nums.length) return 0; if (memo[i][prev + 1] != -1) return memo[i][prev + 1]; int skip = longest(nums, i + 1, prev, memo); int take = 0; if (prev == -1 || nums[i] > nums[prev]) take = 1 + longest(nums, i + 1, i, memo); return memo[i][prev + 1] = Math.max(skip, take); }}For each i, look back at every j < i with nums[j] < nums[i].
- dp[i] = 1 for all i.
- dp[i] = max(dp[i], dp[j] + 1) when nums[j] < nums[i].
- Answer = max over dp.
n(n−1)/2 pairs (i, j).
One array.
class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; // dp[i] = longest increasing subsequence ENDING at i Arrays.fill(dp, 1); // every element alone has length 1 int best = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } best = Math.max(best, dp[i]); } return best; }}Build dp[i]
tails[k] = smallest tail of any increasing run of length k + 1. tails is sorted, so binary-search where each x goes.
- For each x: find the first tails[k] ≥ x.
- Replace it with x (or append if none).
- Answer = number of tails.
One binary search over ≤ n tails per element.
The tails array.
class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; // tails[k] = smallest tail of any increasing run of length k+1 int size = 0; for (int x : nums) { int lo = 0, hi = size; // binary search: first tail >= x while (lo < hi) { int mid = (lo + hi) >>> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; } tails[lo] = x; // replace that tail (or append) if (lo == size) size++; } return size; }}Deal the piles
in the room
How to say it in the interview
talk track
- Start with the O(n²) DP — it's the expected baseline and easy to justify.
- For O(n log n): "a smaller tail is always better for a given length, so keep only the smallest tail per length; that array is sorted → binary search".
- Warn: the tails array is not itself an LIS; only its length is meaningful.
traps
- Strictly increasing: use
tails[mid] < x(lower bound). Using<=would allow equal values. - Answer is max(dp), not dp[n−1].
what they ask next
Follow-ups
Number of LIS (LC 673)?
Keep count[i] alongside dp[i]; add counts when lengths tie.
Russian Doll Envelopes (LC 354)?
Sort by width ascending and height descending, then LIS on heights in O(n log n).
before you submit
Edge cases to test
- All equal → 1 (strictly increasing).
- Sorted ascending → n; sorted descending → 1.
- The LIS can end before the last element: the answer is max(dp), not dp[n − 1].
practise next
Similar problems
- #329Longest Increasing Path in a MatrixHardin Topo Sort
- #1143Longest Common SubsequenceMediumin Dynamic Programming
- #35Search Insert PositionEasyin Binary Search