Start learning free

LESSON 457 OF 540 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence in Kotlin: O(n²) DP

Practice O(n2) Read the full explanation

You are given an array of integers nums. Return the length of its longest strictly increasing subsequence.

A subsequence is what remains after deleting some elements, possibly none, without changing the order of the others. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7]. It is strictly increasing when every element is larger than the one before it, so two equal values can't both be in it.

 

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101] is strictly increasing, and so are [2, 5, 7, 18] and a few others of length 4.
None has 5 elements. Only the length is returned.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: [0, 1, 2, 3] uses the first 0, the 1, the 2 and the last 3.

Example 3:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: Equal values don't increase, so the longest strictly increasing subsequence is a single 7.

 

Constraints:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Note:

Your algorithm should run in O(n2) time and use O(n) extra space, where n is the length of nums.

A faster O(n log n) method exists: keep, for each length, the smallest value that an increasing subsequence of that length can end with, and place every element in that list with a binary search.



Trying every subsequence is far too slow: 2500 elements have 22500 subsequences. Solve smaller versions of the problem instead: let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Every dp[i] is at least 1: the element alone is such a subsequence.

Fill dp from left to right. For every earlier index j < i with nums[j] < nums[i], the element nums[i] can be added to the end of the best subsequence that ends at j, which gives the length dp[j] + 1. So dp[i] is 1 plus the largest such dp[j], or just 1 when no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one.

Every pair j < i is looked at once, and there are n · (n - 1) / 2 pairs: O(n2) time. The table takes O(n) space.
STEP 1 OF 9
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Longest Increasing Subsequence in Kotlin, explained

    Problem overview

    The function lengthOfLIS gets an IntArray named nums and returns the length of its longest strictly increasing subsequence. A subsequence is what is left after deleting some elements, possibly none, without reordering the rest. It is strictly increasing when each element is larger than the one before it, so equal values can't both be in it. Only the length is returned, not the subsequence itself.

    For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4. One longest choice is [2, 3, 7, 101], and [2, 5, 7, 18] is another. For [0, 1, 0, 3, 2, 3] the answer is 4 ([0, 1, 2, 3]), and for [7, 7, 7, 7, 7, 7, 7] it is 1, since equal values never increase.

    Approach

    Checking every subsequence is hopeless: an array of n elements has 2^n of them. Dynamic programming asks a smaller question instead. Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i].

    • Every element alone is a subsequence of length 1, so each dp[i] starts at 1.
    • If an earlier element nums[j] (with j < i) is smaller than nums[i], then nums[i] can follow the best subsequence that ends at j. That gives length dp[j] + 1. Keep the largest such value over all j.

    The subsequence can end anywhere, so the answer is the largest dp[i], not the last one. Each entry reuses the entries before it, and the two nested loops look at every pair j < i once, which gives O(n²) time. A faster O(n log n) method exists: keep, for each length, the smallest value an increasing subsequence of that length can end with, and place every element in that list with a binary search. This lesson uses the table.

    For the first example, the table comes out as follows (from a real run):

    nums = 10 9 2 5 3 7 101 18
dp   =  1 1 1 2 2 3   4  4

    The 7 has dp = 3 because it can follow 5 (which has 2) or 3 (which has 2). The 101 and the 18 both reach 4 by following the 7. The largest entry is 4.

    Step by step

    1. Store the length. val n = nums.size. Both loops run over indexes of nums.
    2. Create the table. IntArray(n) { 1 } makes n entries, each starting at 1. The lambda gives every entry its initial value. No entry is ever below 1, because an element alone is an increasing subsequence.
    3. Track the best. var best = 0 holds the largest length found so far. It is a var because it changes.
    4. Outer loop. for (i in 0 until n) fills the table from left to right. until stops before n, so it covers exactly the valid indexes. Each dp[i] needs only entries to its left, which are final by the time i arrives.
    5. Inner loop. for (j in 0 until i) visits every earlier index. For i = 0 the range is empty and the loop does nothing.
    6. Compare values. if (nums[j] < nums[i]) uses a strict comparison. An equal value can't extend a strictly increasing subsequence.
    7. Update the entry. dp[i] = maxOf(dp[i], dp[j] + 1) keeps the best of all the earlier endings that nums[i] can follow.
    8. Update the best. After the inner loop, dp[i] is final, so best = maxOf(best, dp[i]). This line sits inside the outer loop but outside the inner one.
    9. Return. After the outer loop, return best.

    The solution in Kotlin

    class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n) { 1 }
        var best = 0
        for (i in 0 until n) {
            for (j in 0 until i) {
                if (nums[j] < nums[i]) {
                    dp[i] = maxOf(dp[i], dp[j] + 1)
                }
            }
            best = maxOf(best, dp[i])
        }
        return best
    }
}

    Kotlin details worth knowing:

    • IntArray(n) { 1 } calls the constructor that takes a size and an initializer. Without the lambda, IntArray(n) is filled with zeros, which would be wrong here.
    • IntArray versus Array<Int>. The lesson's parameter is an IntArray, which stores primitive ints. Its size is nums.size, not length.
    • maxOf(a, b) is a standard-library function that returns the larger of two values. It works for Int and other comparable types.
    • 0 until i excludes i. A range written 0..i would include it and compare an element with itself.

    Complexity

    The two loops examine each pair j < i once, which is n · (n - 1) / 2 pairs, so the time is O(n²). With the constraint of at most 2,500 elements, that is about three million comparisons. The table dp takes O(n) extra space.

    Edge cases and common mistakes

    • Using <= instead of <. Equal values would then count as increasing. For [7, 7, 7] the table would reach 3 instead of the correct 1.
    • Returning dp[n - 1]. The best subsequence need not end at the last element. For [1, 2, 3, 0] the table is 1 2 3 1, and the answer is 3, not 1. That is why the solution keeps best.
    • Starting the table at 0. Then an element with no smaller element before it would count as length 0. Start at 1.
    • Single element. [5] gives 1: the inner loop never runs, and best becomes dp[0] = 1.
    • Decreasing input. [5, 4, 3, 2, 1] gives 1, because no earlier element is smaller.
    • Negative values. They need no special care: the loop only compares values. [-3, -2, -1] gives 3.
    • Confusing subsequence with substring. The chosen elements don't have to be next to each other.

    Testing

    Results from running the solution:

    • [10, 9, 2, 5, 3, 7, 101, 18]: 4
    • [0, 1, 0, 3, 2, 3]: 4
    • [7, 7, 7, 7, 7, 7, 7]: 1
    • [5]: 1
    • [5, 4, 3, 2, 1]: 1
    • [1, 2, 3, 4]: 4
    • [-3, -2, -1]: 3
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free