From Brute Force to Binary Search: Mastering Longest Increasing Subsequence

Hello coders,

Let's solve a problem today, don't worry about the pattern or solution just bring a book and a pen or open a whiteboard to illustrate.

Problem for the day:

Alex an adventurous traveller, is preparing for a hiking trip.

Along the trail, there are checkpoints at different elevations.

[10, 9, 2, 5, 3, 7, 101, 18]

Each number represents height at each checkpoint.

The Goal

Alex wants to choose a path such that:

• Each next checkpoint is strictly higher than the previous one

• The path is as long as possible

But there’s a twist:

Alex can skip checkpoints
But cannot go backwards in height

Let's solve this.

At first, understanding the goals we can say that the solution should be the longest sequence which is increasing...

Now this makes straightforward.

Now, a question rises up, How do I build the increasing subsequence?

Approach 1:
I can try all possible subsequences and check which one is increasing and longest.

At this step , I have two choices:
Include the current number in the sequence

Skip it and move forward

This creates a branching structure—a decision tree.

Example run through :
Starting with 10:

• Take 10 → next valid numbers must be greater than 10

• Skip 10 → move to 9

From 9:

• Take 9 → next must be greater than 9

• Skip 9 → move to 2

From 2:

• Take 2 → can go to 5, 3, 7, 101, 18

• Skip 2 → move ahead

and if we construct a decision tree it would look something like this:
Decision Tree (Recursive Exploration)

We represent each node as:

(index, prevValue)

Start:

(0, -∞)

                               (0, -∞)
                              /        \
                     take 10           skip 10
                       |                  |
                   (1,10)             (1,-∞)
                      |               /     \
                  skip 9         take 9     skip 9
                      |            |           |
                   (2,10)       (2,9)       (2,-∞)
                      |            |         /     \
                  skip 2        skip 2   take 2    skip 2
                      |            |       |          |
                   (3,10)       (3,9)    (3,2)     (3,-∞)
                      |            |     /    \      /    \
                  skip 5        skip 5 take 5 skip 5 take 5 skip 5
                      |            |     |      |      |      |
                   (4,10)       (4,9)  (4,5) (4,2)  (4,5)  (4,-∞)

Now, as we found a decision tree we can use a recursive approach to code .

class Solution { 

public int lengthOfLIS(int[] nums) { 
return helper(0, -1, nums); 
}

private int helper(int index, int prevIndex, int[] nums) {
    if (index == nums.length) {
        return 0;
    }
    int notTake = helper(index + 1, prevIndex, nums);
    int take = 0;
    if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
        take = 1 + helper(index + 1, index, nums);
    }
    return Math.max(take, notTake);
}
}

Looking the above code and assess time complexity and space complexity.
Time: O(2ⁿ) and Space: O(n)
For an array of size n:

• We explore almost all possible subsequences

• Each subsequence corresponds to a path in the tree

Total recursive calls ≈ 2ⁿ

Note: Whenever found a problem can be solved with recursive approach try to optimize to memoization and then to tabulation.

Approach 2:
Memoization

From the recursive solution, we observed:

The same states (index, prevIndex) are computed multiple times

So instead of recomputing:

Store the result the first time, and reuse it later

Let's build a state:
dp[index][prevIndex+1] ( here we are using prevIndex+1 cause in our tree we are starting with -1)

class Solution { 
public int lengthOfLIS(int[] nums) { 
     int n = nums.length; 
     Integer[][] dp = new Integer[n][n + 1]; 
     return helper(0, -1, nums, dp); 
}

private int helper(int index, int prevIndex, int[] nums, Integer[][] dp) {
    if (index == nums.length) {
        return 0;
    }

    if (dp[index][prevIndex + 1] != null) {
        return dp[index][prevIndex + 1];
    }

    int notTake = helper(index + 1, prevIndex, nums, dp);

    int take = 0;
    if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
        take = 1 + helper(index + 1, index, nums, dp);
    }

    return dp[index][prevIndex + 1] = Math.max(take, notTake);
}
}

Now the Complexity :

Time Complexity: O(n²)

Space Complexity: O(n²) + O(n) recursion stack

Although memoization improves our solution by avoiding repeated work, it still relies on recursion.

This introduces an overhead of recursive calls and uses the call stack, which can be inefficient for larger inputs.

Which is why we intoduce tabulation here.

At first, it might seem natural to fill the DP table from top to bottom.

But if we try that, we run into a problem.

To compute dp[index][prevIndex], we depend on dp[index + 1][...],
which hasn’t been computed yet.

So we don’t have the required information.

That’s why we reverse our thinking and fill the table from bottom to top,
ensuring that all required states are already computed.

Step 1: State definition
dp[index][prevIndex + 1] = Length of the Longest Increasing Subsequence starting from index, given the last chosen element is at prevIndex

Step 2: Dp relation

Option 1: Skip Current Element

notTake = dp[index + 1][prevIndex + 1]

Option 2: Take Current Element (if valid)

Only if:

prevIndex == -1 OR nums[index] > nums[prevIndex]

Then:

take = 1 + dp[index + 1][index + 1]

Final DP Relation

dp[index][prevIndex + 1] = max(take, notTake)

Step 3:
Base case

dp[n][*]=0

Let's code this now:

    
   class Solution { 
     public int lengthOfLIS(int[] nums) { 
     int n = nums.length;
    int[][] dp = new int[n + 1][n + 1];

    for (int index = n - 1; index >= 0; index--) {
        for (int prevIndex = index - 1; prevIndex >= -1; prevIndex--) {

            int notTake = dp[index + 1][prevIndex + 1];
            int take = 0;
            if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
                take = 1 + dp[index + 1][index + 1];
            }

            dp[index][prevIndex + 1] = Math.max(take, notTake);
        }
    }

    return dp[0][0];
}
}

We are solving the same recurrence as recursion, but iteratively from bottom to top.

Complexity:
Time: O(n²)

Space: O(n²)

Now that Alex has a working solution, something still feels off.

“We improved from exponential to O(n²)… but can we do even better?”

For large inputs, this solution might still be slow.

So the question is:

Can we solve this problem in less than O(n²)?
Instead of tracking all sequences, We focuses on a simpler idea:

For every possible length, what is the smallest ending value of an increasing subsequence?

Why smallest?

Because a smaller ending gives more chances to extend the sequence in the future.

Now the problem changes completely.

Instead of building sequences, we maintain a structure that stores the best possible endings.

And this structure is always sorted.

public static int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;

    for (int num : nums) {
        int left = 0, right = size;

        while (left < right) {
            int mid = (left + right) / 2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        tails[left] = num;
        if (left == size) {
            size++;
        }
    }

    return size;
}

Now, we got the optimized approach which is O(nlogn)