# Longest Increasing Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-increasing-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-increasing-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Atlassian](https://scaleengineer.com/companies/atlassian), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Intuit](https://scaleengineer.com/companies/intuit), [PayPal](https://scaleengineer.com/companies/paypal), [Samsung](https://scaleengineer.com/companies/samsung), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [Commvault](https://scaleengineer.com/companies/commvault), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [Wayfair](https://scaleengineer.com/companies/wayfair), [Flexport](https://scaleengineer.com/companies/flexport), [Splunk](https://scaleengineer.com/companies/splunk), [Druva](https://scaleengineer.com/companies/druva), [Licious](https://scaleengineer.com/companies/licious)
---
## Problem
Given an integer array `nums`, return _the length of the longest **strictly increasing**_ _**subsequence**_.

**Example 1:**

**Input:** nums = [10,9,2,5,3,7,101,18]
**Output:** 4
**Explanation:** The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

**Example 2:**

**Input:** nums = [0,1,0,3,2,3]
**Output:** 4

**Example 3:**

**Input:** nums = [7,7,7,7,7,7,7]
**Output:** 1

**Constraints:**

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

**Follow up:** Can you come up with an algorithm that runs in `O(n log(n))` time complexity?

# Approaches
## Brute Force (Recursive)
The brute force approach involves generating all possible subsequences and finding the longest one that is strictly increasing. We can use recursion to explore all possibilities.
**Time:** O(2^n) - For each element, we have two choices (include or exclude), leading to an exponential number of recursive calls · **Space:** O(n) - The recursion stack can go as deep as the length of the array
**Pros:** Simple to understand and implement; Correctly finds the longest increasing subsequence
**Cons:** Extremely inefficient for larger inputs; Many overlapping subproblems are recomputed; Will exceed time limit for the given constraints
### Explanation
In this approach, we consider each element and make two choices: either include it in the subsequence or exclude it. However, we can only include an element if it's greater than the last element we included.

For each position, we recursively try both including the current element (if valid) and excluding it, then return the maximum length found.

```java
public int lengthOfLIS(int[] nums) {
    // Start the recursion from index 0 with no previous element
    return findLIS(nums, 0, Integer.MIN_VALUE);
}

private int findLIS(int[] nums, int index, int prev) {
    // Base case: reached the end of the array
    if (index == nums.length) {
        return 0;
    }
    
    // Option 1: Skip the current element
    int skip = findLIS(nums, index + 1, prev);
    
    // Option 2: Include the current element if it's greater than the previous element
    int include = 0;
    if (nums[index] > prev) {
        include = 1 + findLIS(nums, index + 1, nums[index]);
    }
    
    // Return the maximum of the two options
    return Math.max(skip, include);
}
```

This solution will work correctly but is extremely inefficient for larger inputs due to the exponential number of recursive calls.
### Algorithm
1. Define a recursive function `findLIS(nums, index, prev)` that returns the length of the LIS starting from `index` with the previous element being `prev`
2. Base case: If `index` reaches the end of the array, return 0
3. For each position, consider two options:
   - Skip the current element and move to the next index
   - Include the current element if it's greater than the previous element
4. Return the maximum of these two options

## Dynamic Programming (Memoization)
We can optimize the recursive approach by using memoization to avoid recomputing the same subproblems multiple times. This is a top-down dynamic programming approach.
**Time:** O(n²) - We have n positions and for each position, we might consider up to n previous indices · **Space:** O(n²) - For the memoization array and recursion stack
**Pros:** Significantly faster than the brute force approach; Avoids recomputing overlapping subproblems; Still maintains the recursive structure which is easy to understand
**Cons:** Still not the most efficient solution possible; Uses more space than necessary; The recursion can lead to stack overflow for very large inputs
### Explanation
The recursive approach has many overlapping subproblems. We can use memoization to store the results of these subproblems and reuse them when needed.

We'll use a 2D array `memo` where `memo[index][prevIndex]` represents the length of the LIS starting from `index` with the previous element at `prevIndex`. Since we need to track the actual previous element's index (not just its value), we'll modify our approach slightly.

```java
public int lengthOfLIS(int[] nums) {
    // Initialize memoization array with -1 (indicating not computed yet)
    Integer[][] memo = new Integer[nums.length][nums.length + 1];
    return findLIS(nums, 0, -1, memo);
}

private int findLIS(int[] nums, int index, int prevIndex, Integer[][] memo) {
    // Base case: reached the end of the array
    if (index == nums.length) {
        return 0;
    }
    
    // If result is already computed, return it
    if (memo[index][prevIndex + 1] != null) {
        return memo[index][prevIndex + 1];
    }
    
    // Option 1: Skip the current element
    int skip = findLIS(nums, index + 1, prevIndex, memo);
    
    // Option 2: Include the current element if it's greater than the previous element
    int include = 0;
    if (prevIndex == -1 || nums[index] > nums[prevIndex]) {
        include = 1 + findLIS(nums, index + 1, index, memo);
    }
    
    // Store the result in memo and return
    memo[index][prevIndex + 1] = Math.max(skip, include);
    return memo[index][prevIndex + 1];
}
```

By using memoization, we significantly reduce the time complexity from exponential to polynomial.
### Algorithm
1. Define a recursive function `findLIS(nums, index, prevIndex, memo)` that returns the length of the LIS starting from `index` with the previous element at `prevIndex`
2. Use a memoization array `memo[index][prevIndex+1]` to store computed results
3. Base case: If `index` reaches the end of the array, return 0
4. If the result for the current state is already in memo, return it
5. For each position, consider two options:
   - Skip the current element and move to the next index
   - Include the current element if it's greater than the previous element
6. Store the maximum of these two options in memo and return it

## Dynamic Programming (Tabulation)
We can use a bottom-up dynamic programming approach to solve this problem more efficiently. This eliminates the recursion overhead and is generally more space-efficient.
**Time:** O(n²) - We have two nested loops, each iterating through the array · **Space:** O(n) - We only need an array of size n to store the dp values
**Pros:** More efficient than the recursive approach; No recursion overhead; Straightforward implementation; Guaranteed to work within the given constraints
**Cons:** Still not the optimal solution in terms of time complexity; For large arrays, O(n²) might still be too slow
### Explanation
In this approach, we define `dp[i]` as the length of the longest increasing subsequence ending at index `i`. For each position `i`, we look at all previous positions `j` (where `j < i`). If `nums[i] > nums[j]`, we can extend the subsequence ending at `j` by including the element at `i`.

```java
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    
    // Initialize dp array with 1 (minimum LIS length is 1)
    Arrays.fill(dp, 1);
    
    int maxLength = 1;
    
    // Fill dp array
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    
    return maxLength;
}
```

This approach is more efficient than the recursive approach with memoization because it eliminates the overhead of recursion and directly computes the results in a bottom-up manner.
### Algorithm
1. Create a dp array of size n, where dp[i] represents the length of the LIS ending at index i
2. Initialize all values in dp to 1 (minimum LIS length is 1)
3. For each position i from 1 to n-1:
   - For each previous position j from 0 to i-1:
     - If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1)
   - Update the maximum LIS length found so far
4. Return the maximum length

## Binary Search with Patience Sort
We can achieve O(n log n) time complexity using a technique similar to patience sort, which uses binary search to efficiently build the longest increasing subsequence.
**Time:** O(n log n) - We process each of the n elements and perform a binary search (log n) for each one · **Space:** O(n) - We need an array of size n to store the tails
**Pros:** Optimal time complexity of O(n log n); Works efficiently for large inputs; Uses less space than the memoization approach; Meets the follow-up challenge requirement
**Cons:** More complex to understand than the DP approaches; The tails array doesn't directly represent the actual LIS (just its length); Requires understanding of patience sort and binary search concepts
### Explanation
This approach maintains a list of piles, where each pile represents the smallest ending value of an increasing subsequence of a certain length. We process each element in the array and use binary search to find the correct pile to place it.

The key insight is that we don't need to keep track of the entire subsequence, just the smallest ending value for subsequences of each length.

```java
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    
    // tails[i] = smallest ending value of all increasing subsequences of length i+1
    int[] tails = new int[n];
    int size = 0; // current number of piles
    
    for (int num : nums) {
        // Binary search to find the correct position for the current number
        int left = 0, right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // Place the current number in the correct position
        tails[left] = num;
        
        // If we created a new pile, increment the size
        if (left == size) {
            size++;
        }
    }
    
    return size;
}
```

This approach is based on the patience sort algorithm. The length of the final tails array (or the number of piles) is the length of the longest increasing subsequence.

Note that the tails array doesn't necessarily represent the actual LIS, but its length is the same as the length of the LIS.
### Algorithm
1. Create an array `tails` where `tails[i]` represents the smallest ending value of all increasing subsequences of length i+1
2. Initialize `size = 0` to track the current number of piles
3. For each number in the input array:
   - Use binary search to find the correct position for the current number in the tails array
   - Place the current number in that position
   - If we created a new pile (i.e., the position is at the end), increment the size
4. Return the final size, which is the length of the LIS

# Solutions
### Java

```java
class Solution { public int lengthOfLIS ( int [] nums ) { int [] s = nums . clone (); Arrays . sort ( s ); int m = 0 ; int n = s . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( i == 0 || s [ i ] != s [ i - 1 ]) { s [ m ++] = s [ i ]; } } BinaryIndexedTree tree = new BinaryIndexedTree ( m ); for ( int x : nums ) { x = search ( s , x , m ); int t = tree . query ( x - 1 ) + 1 ; tree . update ( x , t ); } return tree . query ( m ); } private int search ( int [] nums , int x , int r ) { int l = 0 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] >= x ) { r = mid ; } else { l = mid + 1 ; } } return l + 1 ; } } class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int mx = 0 ; while ( x > 0 ) { mx = Math . max ( mx , c [ x ]); x -= x & - x ; } return mx ; } }
```

### CPP

```cpp
class BinaryIndexedTree { public: BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int v ) { while ( x <= n ) { c [ x ] = max ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int mx = 0 ; while ( x ) { mx = max ( mx , c [ x ]); x -= x & - x ; } return mx ; } private: int n ; vector < int > c ; }; class Solution { public: int lengthOfLIS ( vector < int >& nums ) { vector < int > s = nums ; sort ( s . begin (), s . end ()); s . erase ( unique ( s . begin (), s . end ()), s . end ()); BinaryIndexedTree tree ( s . size ()); for ( int x : nums ) { x = lower_bound ( s . begin (), s . end (), x ) - s . begin () + 1 ; int t = tree . query ( x - 1 ) + 1 ; tree . update ( x , t ); } return tree . query ( s . size ()); } };
```

### Python

```python
# find the largest end element in tails that is smaller than nums[i] # and then replace it with nums[i] and discard the list in the same length # which is implemented by `tail[idx] = num` class Solution ( object ): def lengthOfLIS ( self , nums ): """ :type nums: List[int] :rtype: int """ tail = [] for num in nums : # if using bisect_right(tail, num), # then input=[7,7,7,7,7,7,7] will output 7 but expected result is 1 idx = bisect . bisect_left ( tail , num ) if idx == len ( tail ): # same as in java: if (i == len) len++; tail . append ( num ) else : tail [ idx ] = num return len ( tail ) # implementation of bisect.bisect_left() # similar to Leetcode-302, find left/right/top/bottom callable def bisect_left ( a , x , lo = 0 , hi = None ): if hi is None : hi = len ( a ) while lo < hi : mid = ( lo + hi ) // 2 if a [ mid ] < x : lo = mid + 1 else : hi = mid return lo ############ class BinaryIndexedTree : def __init__ ( self , n : int ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], v ) x += x & - x def query ( self , x : int ) -> int : mx = 0 while x : mx = max ( mx , self . c [ x ]) x -= x & - x return mx class Solution : def lengthOfLIS ( self , nums : List [ int ]) -> int : s = sorted ( set ( nums )) m = len ( s ) tree = BinaryIndexedTree ( m ) for x in nums : x = bisect_left ( s , x ) + 1 t = tree . query ( x - 1 ) + 1 tree . update ( x , t ) return tree . query ( m )
```