Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

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