Given an array A[] consisting of integers [1, N], the task is to count the total number of subarrays of all possible lengths x (1 ? x ? N), consisting of a permutation of integers [1, x] from the given array.
Examples:
Input: A[] = {3, 1, 2, 5, 4} Output: 4
Explanation:
Subarrays forming a permutation are {1}, {1, 2}, {3, 1, 2} and {3, 1, 2, 5, 4}.
Input: A[] = {4, 5, 1, 3, 2, 6} Output: 4
Explanation:
Subarrays forming a permutation are {1}, {1, 3, 2}, {4, 5, 1, 3, 2} and {4, 5, 1, 3, 2, 6}.
Naive Approach:
Follow the steps below to solve the problem:
- The simplest approach to solve the problem is to generate all possible subarrays.
- For each subarray, check if it is a permutation of elements in the range [1, length of subarray].
- For every such subarray found, increase count. Finally, print the count.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, follow the steps below:
- For every element from i = [1, N], check the maximum and minimum index, at which the elements of the permutation [1, i] are present.
- If the difference between the maximum and minimum index is equal to i, then it means there is a valid contiguous permutation for i.
- For every such permutation, increase the count. Finally, print the count.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function returns the required countint PermuteTheArray(int A[], int n){ int arr[n]; // Store the indices of the // elements present in A[]. for (int i = 0; i < n; i++) { arr[A[i] - 1] = i; } // Store the maximum and // minimum index of the // elements from 1 to i. int mini = n, maxi = 0; int count = 0; for (int i = 0; i < n; i++) { // Update maxi and mini, to // store minimum and maximum // index for permutation // of elements from 1 to i+1 mini = min(mini, arr[i]); maxi = max(maxi, arr[i]); // If difference between maxi // and mini is equal to i if (maxi - mini == i) // Increase count count++; } // Return final count return count;}// Driver Codeint main(){ int A[] = { 4, 5, 1, 3, 2, 6 }; cout << PermuteTheArray(A, 6); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function returns the required countstatic int PermuteTheArray(int A[], int n){ int []arr = new int[n]; // Store the indices of the // elements present in A[]. for(int i = 0; i < n; i++) { arr[A[i] - 1] = i; } // Store the maximum and // minimum index of the // elements from 1 to i. int mini = n, maxi = 0; int count = 0; for(int i = 0; i < n; i++) { // Update maxi and mini, to // store minimum and maximum // index for permutation // of elements from 1 to i+1 mini = Math.min(mini, arr[i]); maxi = Math.max(maxi, arr[i]); // If difference between maxi // and mini is equal to i if (maxi - mini == i) // Increase count count++; } // Return final count return count;}// Driver Codepublic static void main(String[] args){ int A[] = { 4, 5, 1, 3, 2, 6 }; System.out.print(PermuteTheArray(A, 6));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement# the above approach# Function returns the required countdef PermuteTheArray(A, n): arr = [0] * n # Store the indices of the # elements present in A[]. for i in range(n): arr[A[i] - 1] = i # Store the maximum and # minimum index of the # elements from 1 to i. mini = n maxi = 0 count = 0 for i in range(n): # Update maxi and mini, to # store minimum and maximum # index for permutation # of elements from 1 to i+1 mini = min(mini, arr[i]) maxi = max(maxi, arr[i]) # If difference between maxi # and mini is equal to i if (maxi - mini == i): # Increase count count += 1 # Return final count return count# Driver Codeif __name__ == "__main__": A = [ 4, 5, 1, 3, 2, 6 ] print(PermuteTheArray(A, 6))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function returns the required countstatic int PermuteTheArray(int []A, int n){ int []arr = new int[n]; // Store the indices of the // elements present in []A. for(int i = 0; i < n; i++) { arr[A[i] - 1] = i; } // Store the maximum and // minimum index of the // elements from 1 to i. int mini = n, maxi = 0; int count = 0; for(int i = 0; i < n; i++) { // Update maxi and mini, to // store minimum and maximum // index for permutation // of elements from 1 to i+1 mini = Math.Min(mini, arr[i]); maxi = Math.Max(maxi, arr[i]); // If difference between maxi // and mini is equal to i if (maxi - mini == i) // Increase count count++; } // Return final count return count;}// Driver Codepublic static void Main(String[] args){ int []A = { 4, 5, 1, 3, 2, 6 }; Console.Write(PermuteTheArray(A, 6));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript Program to implement// the above approach// Function returns the required countfunction PermuteTheArray(A, n){ var arr = Array(n); // Store the indices of the // elements present in A[]. for (var i = 0; i < n; i++) { arr[A[i] - 1] = i; } // Store the maximum and // minimum index of the // elements from 1 to i. var mini = n, maxi = 0; var count = 0; for (var i = 0; i < n; i++) { // Update maxi and mini, to // store minimum and maximum // index for permutation // of elements from 1 to i+1 mini = Math.min(mini, arr[i]); maxi = Math.max(maxi, arr[i]); // If difference between maxi // and mini is equal to i if (maxi - mini == i) // Increase count count++; } // Return final count return count;}// Driver Codevar A = [4, 5, 1, 3, 2, 6];document.write( PermuteTheArray(A, 6));</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: 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!
