Longest Increasing Subsequence
Medium About 25 min Free, no account needed
Length of the longest strictly increasing subsequence - faster than the quadratic DP.
The brief
Given an integer array nums, return the length of its longest strictly
increasing subsequence (not necessarily contiguous).
The obvious approach compares each element against all earlier ones, O(n2), and the hidden test has 100,000 elements arranged so it never short-circuits, so it times out. You will need a solution that runs in O(n log n).
Starter code
using System;
public class Solution
{
// TODO: return the length of the longest strictly increasing subsequence.
public int LengthOfLIS(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
- Binary search
- Halve a sorted search space, with exact boundaries and no off-by-one drift.
Related katas
- Minimum Travel Pass Cost Medium Free Cover sparse travel dates with overlapping pass durations while paying for no unnecessary calendar state.
- Weighted Reservation Schedule Hard Free Choose a maximum-value set of nonoverlapping reservations with a mandatory cleanup gap.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Coin Change II (Count the Ways) Medium Free How many coin combinations make the amount?