Problem Statement

Given an array of n integers arr, return the Longest Increasing Subsequence (LIS) that is index-wise Lexicographically Smallest.

The Longest Increasing Subsequence (LIS) is the longest subsequence where all elements are in strictly increasing order.

A subsequence A1 is index-wise Lexicographically Smaller than another subsequence A2 if, at the first position where A1 and A1 differ, the element in A1 appears earlier in the array arr than corresponding element in S2.

Your task is to return the LIS that is Index-wise Lexicographically Smallest from the given array.

Examples

Example 1:

Input: arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
Output: [10, 22, 33, 50, 60, 80]

Explanation: The LIS is [10, 22, 33, 50, 60, 89] and it is the lexicographically smallest.

Example 2:

Input: arr = [1, 3, 2, 4, 6, 5]
Output: [1, 3, 4, 6]

Explanation: Possible LIS sequences are [1, 3, 4, 6] and [1, 2, 4, 6]. Since [1, 3, 4, 6] is Index-wise Lexicographically Smaller, it is the result.

Different Approaches

1️⃣ Tabulation

Intuition:

In order to print the LIS, we cannot use the traditional tabulation approach (converting memoization to tabulation) or the space-optimized approach. To get to our answer, we need to understand a different tabulation approach, which will help us retrace the LIS formed.

We will use a 1D DP array to store the last index of the LIS formed till now, where dp[i] will store the length of longest increasing subsequence that ends at index i.

How to compute the DP array?

We will iterate through the array and for each index i, we will check all the previous indices j (0 to i-1). If arr[j] < arr[i], we will update dp[i] = max(dp[i], dp[j] + 1). This means that if arr[j] is less than arr[i], then we can extend the LIS formed till index j by including arr[i].

Backtracking:

Now, since we have understood the tabulation method, we can keep a parent array that will help backtrack and eventually help us print the LIS. Whenever we update dp[i], we will also update the parent array.

The parent array will store the index of the previous element in the LIS. So, if we are at index i and we find that arr[j] < arr[i], we will set parent[i] = j. This means that the previous element in the LIS ending at index i is at index j.

Note that the LIS found by this approach will be in reverse order. So, we will need to reverse the LIS before returning it.

Approach:

1. Initialize tracking structures to store the length of the longest subsequence ending at each position and to remember the previous index for reconstruction.
2. Iterate through the array, and for each element, check all previous elements to see if it can extend an increasing subsequence. If yes, update the length and store the previous index.
3. Track the maximum length of the increasing subsequence and its ending position.
4. Backtrack from the ending position using the parent links to reconstruct the actual subsequence.
5. Reverse the sequence to get it in the correct order and return it.

Code:

 class Solution {
  public:
    vector<int> longestIncreasingSubsequence(vector<int>& arr) {

    int n = arr.size(); // Get the size of the array

    // t[i] will store the length of the longest increasing subsequence ending at index i
    vector<int> t(n, 1);

    // parent[i] will store the index of the previous element in the LIS ending at i
    vector<int> parent(n);

    // Initially, each element is its own parent (a subsequence of length 1)
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }

    int longestIdx = 0; // Index where the LIS ends
    int maxi = 1;       // Length of the longest subsequence found so far

    // Build the DP and parent arrays
    for (int i = 0; i < n; i++) {
      for (int j = 0;  j < i; j++) {
        // If arr[i] can extend the increasing subsequence ending at arr[j]
        if (arr[j] < arr[i] && (t[j] + 1) > t[i]) {
          t[i] = t[j] + 1;       // Update the length of LIS ending at i
          parent[i] = j;         // Update the parent of i
        }

        // If the new LIS ending at i is the longest so far
        if (t[i] > maxi) {
          maxi = t[i];           // Update the maximum length
          longestIdx = i;        // Update the index where LIS ends
        }
      }
    }

    // Reconstruct the LIS by backtracking using the parent array
    vector<int> ans;
    while (longestIdx != parent[longestIdx]) {
      ans.push_back(arr[longestIdx]); // Add current element to the answer
      longestIdx = parent[longestIdx]; // Move to the previous element
    }
    ans.push_back(arr[longestIdx]); // Add the first element of the LIS

    reverse(ans.begin(), ans.end()); // The sequence was built in reverse, so reverse it

    return ans; // Return the reconstructed LIS
  }
};

Complexity Analysis:

• Time Complexity:O(N^2), where N is the size of the given array.
  • Computing the DP array takes O(N^2) time, and backtracking the LIS takes O(N) time.
• Space Complexity:O(N), because of two arrays (dp and parent) used, each of size N.