Given an array arr[] of integers, the task is to find the length of the second longest increasing subsequence (LIS).
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 3
Explanation: Here the length of LIS is 4 which is whole array and length of second LIS is 3 which can be any sequence, {1, 2, 3} or {1, 2, 4} or {1, 3, 4} or {2, 3, 4}.Input: arr[] = {1, -4, 3, 5, 9}
Output: 4
Explanation: Here the length of LIS is 4. Second LIS is also 4, because there can be two sequence in this case with length 4. One is {1, 3, 5, 9} and second is {-4, 3, 5, 9}.
Approach: To solve the problem follow the below idea:
- In order to solve this problem we first find the length of the longest increasing subsequence(LIS). This can be done with a time complexity of O(n^2) using dynamic programming. Along with this, we find the count of the number of subsequences which has a length of LIS. Here is an article where the approach to find the count of LIS.
- After finding the count of LIS in an array we check if the count of such subsequence with same length of LIS is more than two or not, if yes then it means that more than one LIS is present and hence the length of the second longest subsequence will also be lengthOfLis. If the count is not greater than 1 then the second longest subsequence can be lengthOfLis -1 as the second longest subsequence can be subset of LIS with any one element excluded.
Steps involved in the implementation of the code:
- Initialize two arrays dpL[] and dpC[]. Here dpL[] stores the length of the longest increasing subsequences and dpC[] stores the count of the longest increasing subsequence at each index respectively.
- Traverse the array using two loops where variable i iterates from 0 to n-1 and variable j iterates from 0 to i – 1.
- If arr[i] > arr[j] then check for the following two cases.
- If (dpL[j]+1) is greater than dpL[i], then update dpL[i] as dpL[j] + 1 and dpC[i] as dpC[j].
- Else if (dpL[j] + 1) is the same as dpL[i], then update dpC[i] as dpC[i] + dpC[j].
- Then find the maximum element in the array dpL[] and store it in a variable maxLength as it is the longest increasing subsequence.
- Initialize a variable count with 0 to store the number of the longest increasing subsequence. Then traverse the array dpL[] and if at any index i, dpL[i] is the same as maxLength then increment the count by dpC[i].
- If the count of the longest increasing subsequence is greater than 1 then return maxLength else return maxLength – 1.
Below is the implementation for the above approach:
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the second
// longest increasing subsequence
int secondLis(int arr[], int n)
{
// Initialize dpL array with
// 1 which Store the length of
// the longest increasing subsequences
vector<int> dpL(n, 1);
// Initialize dpC array with
// 1 which store the count of
// the longest increasing
// subsequence at each index
vector<int> dpC(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
// If current element is
// smaller
if (arr[i] <= arr[j])
continue;
if (dpL[j] + 1 > dpL[i]) {
// If new longer lis found,
// update current length
// max upto this index as
// dpL[j]+1, and also
// update count of current
// size as that of dpC[j]th
dpL[i] = dpL[j] + 1;
dpC[i] = dpC[j];
}
else if (dpL[j] + 1 == dpL[i])
// Else if similar length,
// add up ith index count
// with jth.
dpC[i] += dpC[j];
}
}
// Finding length of LIS
int maxLength = 0;
for (int i : dpL)
maxLength = max(i, maxLength);
// Stores the count of LIS
int count = 0;
// Finding count
for (int i = 0; i < n; i++) {
// Update the count
if (dpL[i] == maxLength)
count += dpC[i];
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
return maxLength;
}
else {
return maxLength - 1;
}
}
// Driver's code
int main()
{
int arr[] = { 1, -4, 3, 5, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Length of second longest increasing "
"subsequence is %d\n",
secondLis(arr, n));
return 0;
}
Java
// Java code for above approach
import java.util.*;
class GFG {
// Function to find the second
// longest increasing subsequence
public static int secondLis(int arr[], int n)
{
// Initialize dpL array with
// 1 which Store the length of
// the longest increasing subsequences
int dpL[] = new int[n];
Arrays.fill(dpL, 1);
// Initialize dpC array with
// 1 which store the count of
// the longest increasing
// subsequence at each index
int dpC[] = new int[n];
Arrays.fill(dpC, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
// If current element is
// smaller
if (arr[i] <= arr[j])
continue;
if (dpL[j] + 1 > dpL[i]) {
// If new longer lis found,
// update current length
// max upto this index as
// dpL[j]+1, and also
// update count of current
// size as that of dpC[j]th
dpL[i] = dpL[j] + 1;
dpC[i] = dpC[j];
}
else if (dpL[j] + 1 == dpL[i]) {
// Else if similar length,
// add up ith index count
// with jth.
dpC[i] += dpC[j];
}
}
}
// Finding length of LIS
int maxLength = 0;
for (int i : dpL) {
maxLength = Math.max(i, maxLength);
}
// Stores the count of LIS
int count = 0;
// Finding count
for (int i = 0; i < n; i++) {
// Update the count
if (dpL[i] == maxLength)
count += dpC[i];
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
return maxLength;
}
else {
return maxLength - 1;
}
}
public static void main(String[] args)
{
int arr[] = { 1, -4, 3, 5, 9 };
int n = arr.length;
System.out.printf(
"Length of second longest increasing subsequence is %d\n",
secondLis(arr, n));
}
}
// This code is contributed by Prasad Kandekar(prasad264)
Python3
# Python code implementation:
import sys
# Function to find the second longest increasing subsequence
def second_lis(arr, n):
# Initialize dpL array with 1 which Store the
# length of the longest increasing subsequences
dpL = [1]*n
# Initialize dpC array with 1 which store the
# count of the longest increasing subsequence
# at each index
dpC = [1]*n
for i in range(n):
for j in range(i):
# If current element is smaller
if arr[i] <= arr[j]:
continue
if dpL[j] + 1 > dpL[i]:
# If new longer lis found, update current
# length max upto this index as dpL[j]+1,
# and also update count of current size as
# that of dpC[j]th
dpL[i] = dpL[j] + 1
dpC[i] = dpC[j]
elif dpL[j] + 1 == dpL[i]:
# Else if similar length, add up ith index
# count with jth.
dpC[i] += dpC[j]
# Finding length of LIS
max_length = max(dpL)
# Stores the count of LIS
count = 0
# Finding count
for i in range(n):
# Update the count
if dpL[i] == max_length:
count += dpC[i]
# If count is more than 1 LIS then second
# longest will be same as length of LIS(maxLength)
# else it will be maxLength-1
if count > 1:
return max_length
else:
return max_length - 1
arr = [1, -4, 3, 5, 9]
n = len(arr)
print("Length of second longest increasing subsequence is", second_lis(arr, n))
# This code is contributed by sankar.
C#
// C# code for above approach
using System;
public class GFG {
// Function to find the second
// longest increasing subsequence
public static int secondLis(int[] arr, int n)
{
// Initialize dpL array with
// 1 which Store the length of
// the longest increasing subsequences
int[] dpL = new int[n];
Array.Fill(dpL, 1);
// Initialize dpC array with
// 1 which store the count of
// the longest increasing
// subsequence at each index
int[] dpC = new int[n];
Array.Fill(dpC, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
// If current element is
// smaller
if (arr[i] <= arr[j])
continue;
if (dpL[j] + 1 > dpL[i]) {
// If new longer lis found,
// update current length
// max upto this index as
// dpL[j]+1, and also
// update count of current
// size as that of dpC[j]th
dpL[i] = dpL[j] + 1;
dpC[i] = dpC[j];
}
else if (dpL[j] + 1 == dpL[i]) {
// Else if similar length,
// add up ith index count
// with jth.
dpC[i] += dpC[j];
}
}
}
// Finding length of LIS
int maxLength = 0;
foreach(int i in dpL)
{
maxLength = Math.Max(i, maxLength);
}
// Stores the count of LIS
int count = 0;
// Finding count
for (int i = 0; i < n; i++) {
// Update the count
if (dpL[i] == maxLength)
count += dpC[i];
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
return maxLength;
}
else {
return maxLength - 1;
}
}
// Driver Code
static public void Main()
{
int[] arr = { 1, -4, 3, 5, 9 };
int n = arr.Length;
Console.WriteLine(
"Length of second longest increasing subsequence is "
+ secondLis(arr, n));
}
}
// This code is contributed by Rohit Pradhan
Javascript
// Javascript code for above approach
// Function to find the second
// longest increasing subsequence
function secondLis(arr) {
const n = arr.length;
// Initialize dpL array with
// 1 which Store the length of
// the longest increasing subsequences
const dpL = new Array(n).fill(1);
// Initialize dpC array with
// 1 which store the count of
// the longest increasing
// subsequence at each index
const dpC = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
// If current element is
// smaller
if (arr[i] <= arr[j])
continue;
if (dpL[j] + 1 > dpL[i]) {
// If new longer lis found,
// update current length
// max upto this index as
// dpL[j]+1, and also
// update count of current
// size as that of dpC[j]th
dpL[i] = dpL[j] + 1;
dpC[i] = dpC[j];
}
else if (dpL[j] + 1 == dpL[i]) {
// Else if similar length,
// add up ith index count
// with jth.
dpC[i] += dpC[j];
}
}
}
// Finding length of LIS
let maxLength = 0;
for (let i of dpL)
maxLength = Math.max(i, maxLength);
// Stores the count of LIS
let count = 0;
// Finding count
for (let i = 0; i < n; i++) {
// Update the count
if (dpL[i] == maxLength)
count += dpC[i];
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
return maxLength;
}
else {
return maxLength - 1;
}
}
// Driver's code
const arr = [1, -4, 3, 5, 9];
console.log(`Length of second longest increasing subsequence is ${secondLis(arr)}`);
Output
Length of second longest increasing subsequence is 4
Time Complexity: O(N2)
Auxiliary Space: O(N)
Memoised Dynamic Programming Approach:
We can also solve the problem using memoised approach of dynamic programming.
The algorithm for the implementation is as follows:
- Initialize the input array arr[] and its size n.
- Create two empty vectors dpL and dpC, each of size n, and initialize them to -1.
- Define a function secondLis(arr, n, dpL, dpC) to compute the length of the second longest increasing subsequence for the nth index of the input array.
a. If dpL[n] is already calculated, return dpL[n].
b. Otherwise, set dpL[n] and dpC[n] to 1.
c. Iterate over all indices i less than n:
If arr[n] is greater than arr[i]:
Compute the length of the second longest increasing subsequence for index i by calling secondLis(arr, i, dpL, dpC).
If the length of the LIS for index i plus 1 is greater than dpL[n], update dpL[n] to be len + 1 and dpC[n] to be dpC[i].
If the length of the LIS for index i plus 1 is equal to dpL[n], update dpC[n] to be dpC[n] + dpC[i].
d. Return dpL[n]. - Define the main function:
a. Initialize maxLength to 0 and count to 0.
b. Iterate over all indices i from 0 to n – 1:
i. Compute the length of the second longest increasing subsequence for index i by calling secondLis(arr, i, dpL, dpC).
ii. If the length is greater than maxLength, update maxLength to be the length and count to be dpC[i].
iii. If the length is equal to maxLength, update count to be count + dpC[i].
c. If count is greater than 1, print “Length of second longest increasing subsequence is maxLength”.
d. Otherwise, print “Length of second longest increasing subsequence is maxLength – 1”.
Below is the implementation of the algorithm:
C++
// C++ code for the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the second longest increasing subsequence
int secondLis(int arr[], int n, vector<int>& dpL, vector<int>& dpC) {
// If dpL[i] is already calculated, return it
if (dpL[n] != -1)
return dpL[n];
// Otherwise, compute dpL[i] and dpC[i] values
dpL[n] = 1;
dpC[n] = 1;
for (int i = 0; i < n; i++) {
if (arr[n] > arr[i]) {
int len = secondLis(arr, i, dpL, dpC);
if (len + 1 > dpL[n]) {
dpL[n] = len + 1;
dpC[n] = dpC[i];
}
else if (len + 1 == dpL[n]) {
dpC[n] += dpC[i];
}
}
}
return dpL[n];
}
// Driver's code
int main() {
int arr[] = { 1, -4, 3, 5, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
// Initialize dpL and dpC arrays with -1
vector<int> dpL(n, -1);
vector<int> dpC(n, -1);
// Compute dpL and dpC values for each index
int maxLength = 0, count = 0;
for (int i = 0; i < n; i++) {
int len = secondLis(arr, i, dpL, dpC);
if (len > maxLength) {
maxLength = len;
count = dpC[i];
}
else if (len == maxLength) {
count += dpC[i];
}
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
cout << "Length of second longest increasing subsequence is " << maxLength << endl;
}
else {
cout << "Length of second longest increasing subsequence is " << maxLength - 1 << endl;
}
return 0;
}
Java
// Java code for the approach
import java.util.*;
class GFG
{
// Function to find the second longest increasing
// subsequence
public static int secondLis(int arr[], int n, int[] dpL,
int[] dpC) {
// If dpL[i] is already calculated, return it
if (dpL[n] != -1)
return dpL[n];
// Otherwise, compute dpL[i] and dpC[i] values
dpL[n] = 1;
dpC[n] = 1;
for (int i = 0; i < n; i++) {
if (arr[n] > arr[i]) {
int len = secondLis(arr, i, dpL, dpC);
if (len + 1 > dpL[n]) {
dpL[n] = len + 1;
dpC[n] = dpC[i];
}
else if (len + 1 == dpL[n]) {
dpC[n] += dpC[i];
}
}
}
return dpL[n];
}
// Driver's code
public static void main(String[] args) {
int arr[] = { 1, -4, 3, 5, 9 };
int n = arr.length;
// Initialize dpL and dpC arrays with -1
int[] dpL = new int[n];
int[] dpC = new int[n];
Arrays.fill(dpL, -1);
Arrays.fill(dpC, -1);
// Compute dpL and dpC values for each index
int maxLength = 0, count = 0;
for (int i = 0; i < n; i++) {
int len = secondLis(arr, i, dpL, dpC);
if (len > maxLength) {
maxLength = len;
count = dpC[i];
}
else if (len == maxLength) {
count += dpC[i];
}
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
System.out.println(
"Length of second longest increasing subsequence is "
+ maxLength);
}
else {
System.out.println(
"Length of second longest increasing subsequence is "
+ (maxLength - 1));
}
}
}
Python3
# Python3 code for the approach
# Function to find the second longest increasing subsequence
def secondLis(arr):
n = len(arr)
# Initialize dpL and dpC arrays with -1
dpL = [-1]*n
dpC = [-1]*n
# If dpL[i] is already calculated, return it
def dp(n):
if dpL[n] != -1:
return dpL[n]
# Otherwise, compute dpL[i] and dpC[i] values
dpL[n] = 1
dpC[n] = 1
for i in range(n):
if arr[n] > arr[i]:
length = dp(i)
if length + 1 > dpL[n]:
dpL[n] = length + 1
dpC[n] = dpC[i]
elif length + 1 == dpL[n]:
dpC[n] += dpC[i]
return dpL[n]
# Compute dpL and dpC values for each index
maxLength = 0
count = 0
for i in range(n):
length = dp(i)
if length > maxLength:
maxLength = length
count = dpC[i]
elif length == maxLength:
count += dpC[i]
# If count is more than 1 LIS
# then second longest will be
# same as length of LIS(maxLength)
# else it will be maxLength-1
if count > 1:
print("Length of second longest increasing subsequence is", maxLength)
else:
print("Length of second longest increasing subsequence is", maxLength-1)
# Driver's code
if __name__ == '__main__':
# Input array
arr = [1, -4, 3, 5, 9]
# Function Call
secondLis(arr)
C#
using System;
public class GFG
{
// Function to find the second longest increasing
// subsequence
public static int SecondLis(int[] arr, int n, int[] dpL, int[] dpC)
{
// If dpL[i] is already calculated, return it
if (dpL[n] != -1)
return dpL[n];
// Otherwise, compute dpL[i] and dpC[i] values
dpL[n] = 1;
dpC[n] = 1;
for (int i = 0; i < n; i++)
{
if (arr[n] > arr[i])
{
int len = SecondLis(arr, i, dpL, dpC);
if (len + 1 > dpL[n])
{
dpL[n] = len + 1;
dpC[n] = dpC[i];
}
else if (len + 1 == dpL[n])
{
dpC[n] += dpC[i];
}
}
}
return dpL[n];
}
// Driver's code
public static void Main(string[] args)
{
int[] arr = { 1, -4, 3, 5, 9 };
int n = arr.Length;
// Initialize dpL and dpC arrays with -1
int[] dpL = new int[n];
int[] dpC = new int[n];
for (int i = 0; i < n; i++)
{
dpL[i] = -1;
dpC[i] = -1;
}
// Compute dpL and dpC values for each index
int maxLength = 0, count = 0;
for (int i = 0; i < n; i++)
{
int len = SecondLis(arr, i, dpL, dpC);
if (len > maxLength)
{
maxLength = len;
count = dpC[i];
}
else if (len == maxLength)
{
count += dpC[i];
}
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1)
{
Console.WriteLine(
"Length of second longest increasing subsequence is " + maxLength);
}
else
{
Console.WriteLine(
"Length of second longest increasing subsequence is " + (maxLength - 1));
}
}
}
Javascript
// JavaScript code for the approach
// Function to find the second longest increasing subsequence
function secondLis(arr) {
const n = arr.length;
// Initialize dpL and dpC arrays with -1
const dpL = Array(n).fill(-1);
const dpC = Array(n).fill(-1);
// Function to find the second longest increasing subsequence
function secondLisHelper(n) {
// If dpL[i] is already calculated, return it
if (dpL[n] !== -1)
return dpL[n];
// Otherwise, compute dpL[i] and dpC[i] values
dpL[n] = 1;
dpC[n] = 1;
for (let i = 0; i < n; i++) {
if (arr[n] > arr[i]) {
const len = secondLisHelper(i);
if (len + 1 > dpL[n]) {
dpL[n] = len + 1;
dpC[n] = dpC[i];
}
else if (len + 1 === dpL[n]) {
dpC[n] += dpC[i];
}
}
}
return dpL[n];
}
// Compute dpL and dpC values for each index
let maxLength = 0, count = 0;
for (let i = 0; i < n; i++) {
const len = secondLisHelper(i);
if (len > maxLength) {
maxLength = len;
count = dpC[i];
}
else if (len === maxLength) {
count += dpC[i];
}
}
// If count is more than 1 LIS
// then second longest will be
// same as length of LIS(maxLength)
// else it will be maxLength-1
if (count > 1) {
console.log(`Length of second longest increasing subsequence is ${maxLength}`);
}
else {
console.log(`Length of second longest increasing subsequence is ${maxLength - 1}`);
}
}
// Driver's code
const arr = [1, -4, 3, 5, 9];
secondLis(arr);
Output
Length of second longest increasing subsequence is 4
Time Complexity: O(n*n) where n is size of input array.
Auxiliary Space: O(n) as 1D vectors dpL and dpC are created.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
