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 subsequenceint 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 Codeint 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 arrayimport java.util.*;class GFG{ // Function to find the// longest permutation subsequencestatic 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 Codepublic 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 arrayusing System;using System.Collections.Generic;public class GFG{// Function to find the// longest permutation subsequencestatic 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 Codepublic 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 arrayfrom collections import defaultdict# Function to find the# longest permutation subsequencedef 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 Codeif __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 subsequencefunction 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:
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
