Longest permutation subsequence in a given array

0 0 4 minutes read

Given an array arr containing N elements, find the length of the longest subsequence such that it is a valid permutation of a particular length. If no such permutation sequence exists then print 0.
Examples:

Input: arr[] = {3, 2, 1, 6, 5}
Output: 3
Explanation:
Longest permutation subsequence will be [3, 2, 1].
Input: arr[]= {2, 3, 4, 5}
Output: 0
Explanation:
No valid permutation subsequence present as element 1 is missing.

Approach: The above-mentioned problem is on permutation subsequence so the order of the array elements is irrelevant, only what matter is the frequency of each element. If array is of length N then the maximum possible length for the permutation sequence is N and minimum possible length is 0. If the subsequence of length L is a valid permutation then all elements from 1 to L should be present.

Count the frequency of the elements in the range [1, N] from the array
Iterate through all elements from 1 to N in the array and count the iterations till a 0 frequency is observed. If the frequency of an element is ‘0’, return the current count of iterations as the required length.

Below is the implementation of the above approach:

C++

// C++ Program to find length of
// Longest Permutation Subsequence
// in a given array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// longest permutation subsequence
int longestPermutation(int a[], int n)
{
 
    // Map data structure to
    // count the frequency of each element
    map<int, int> freq;
 
    for (int i = 0; i < n; i++) {
 
        freq[a[i]]++;
    }
 
    int len = 0;
 
    for (int i = 1; i <= n; i++) {
 
        // If frequency of element is 0,
        // then we can not move forward
        // as every element should be present
        if (freq[i] == 0) {
            break;
        }
 
        // Increasing the length by one
        len++;
    }
 
    return len;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 3, 2, 1, 6, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << longestPermutation(arr, n)
         << "\n";
 
    return 0;
}

Java

// Java Program to find length of
// Longest Permutation Subsequence
// in a given array
import java.util.*;
 
class GFG{
  
// Function to find the
// longest permutation subsequence
static int longestPermutation(int arr[], int n)
{
  
    // Map data structure to
    // count the frequency of each element
    HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
  
    for (int i = 0; i < n; i++) {
  
        if(freq.containsKey(arr[i])){
            freq.put(arr[i], freq.get(arr[i])+1);
        }else{
            freq.put(arr[i], 1);
        }
    }
  
    int len = 0;
  
    for (int i = 1; i <= n; i++) {
  
        // If frequency of element is 0,
        // then we can not move forward
        // as every element should be present
        if (!freq.containsKey(i)) {
            break;
        }
  
        // Increasing the length by one
        len++;
    }
  
    return len;
}
  
// Driver Code
public static void main(String[] args)
{
  
    int arr[] = { 3, 2, 1, 6, 5 };
    int n = arr.length;
  
    System.out.print(longestPermutation(arr, n));
  
}
}
 
// This code is contributed by Rajput-Ji

C#

// C# Program to find length of
// longest Permutation Subsequence
// in a given array
 
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Function to find the
// longest permutation subsequence
static int longestPermutation(int []arr, int n)
{
 
    // Map data structure to
    // count the frequency of each element
    Dictionary<int,int> freq = new Dictionary<int,int>();
 
    for (int i = 0; i < n; i++) {
 
        if(freq.ContainsKey(arr[i])){
            freq[arr[i]] = freq[arr[i]] + 1;
        }else{
            freq.Add(arr[i], 1);
        }
    }
 
    int len = 0;
 
    for (int i = 1; i <= n; i++) {
 
        // If frequency of element is 0,
        // then we can not move forward
        // as every element should be present
        if (!freq.ContainsKey(i)) {
            break;
        }
 
        // Increasing the length by one
        len++;
    }
 
    return len;
}
 
// Driver Code
public static void Main(String[] args)
{
 
    int []arr = { 3, 2, 1, 6, 5 };
    int n = arr.Length;
 
    Console.Write(longestPermutation(arr, n));
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Program to find length of
# Longest Permutation Subsequence
# in a given array
from collections import defaultdict
 
# Function to find the
# longest permutation subsequence
def longestPermutation(a, n):
  
    # Map data structure to
    # count the frequency of each element
    freq = defaultdict(int)
  
    for i in range( n ):
  
        freq[a[i]] += 1
  
    length = 0
  
    for i in range(1 , n + 1):
  
        # If frequency of element is 0,
        # then we can not move forward
        # as every element should be present
        if (freq[i] == 0):
            break
  
        # Increasing the length by one
        length += 1
         
    return length
  
# Driver Code
if __name__ == "__main__":
  
    arr = [ 3, 2, 1, 6, 5 ]
    n = len(arr)
  
    print(longestPermutation(arr, n))
 
# This code is contributed by chitranayal

Javascript

<script>
 
// Javascript Program to find length of
// Longest Permutation Subsequence
// in a given array
 
// Function to find the
// longest permutation subsequence
function longestPermutation(arr, n)
{
    
    // Map data structure to
    // count the frequency of each element
    let freq = new Map();
    
    for (let i = 0; i < n; i++) {
    
        if(freq.has(arr[i])){
            freq.set(arr[i], freq.get(arr[i])+1);
        }else{
            freq.set(arr[i], 1);
        }
    }
    
    let len = 0;
    
    for (let i = 1; i <= n; i++) {
    
        // If frequency of element is 0,
        // then we can not move forward
        // as every element should be present
        if (!freq.has(i)) {
            break;
        }
    
        // Increasing the length by one
        len++;
    }
    
    return len;
}
  
// Driver code
     
      let arr = [ 3, 2, 1, 6, 5 ];
    let n = arr.length;
    
    document.write(longestPermutation(arr, n));
                                                                                       
</script>

Output:

Time Complexity: O(N)
Auxiliary Space Complexity: O(N)

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 zambiatek!