Count of subarrays of size K which is a permutation of numbers from 1 to K

0 0 5 minutes read

Given an array arr of distinct integers, the task is to find the count of sub-arrays of size i having all elements from 1 to i, in other words, the sub-array is any permutation of elements from 1 to i, with 1 < = i <= N.

Examples:

Input: arr[] = {2, 3, 1, 5, 4}
Output: 3
Explanation:
we have {1}, {2, 3, 1} and {2, 3, 1, 5, 4} subarray for i=1, i=3, i=5 respectively.
Permutation of size 4 and size 2 can’t be made because 5 and 3 are in the way respectively.

Input: arr[] = {1, 3, 5, 4, 2}
Output: 2
Explanation:
we have {1} and {1, 3, 5, 4, 2} subarray for i=1 and i=5 respectively.

A Naive approach is to start from each index and try to find the subarray of every size(i) and check whether all elements from 1 to i are present.
Time complexity: O(N²)

An Efficient approach can be given by checking if it is possible to create a subarray of size i for every value of i from 1 to N.
As we know, every subarray of size K must be a permutation of all elements from 1 to K, knowing that we can look at the index of the numbers from 1 to N in order and calculate the index of the minimum and maximum values at every step.

If maximum_ind – minimum_ind + 1 = K, then we have a permutation of size K, else not.
Update the value of minimum_ind and maximum_ind at every step.

Time complexity: O(n)
Illustration:

Given Arr = {2, 3, 1, 5, 4}, let’s start with min_ind = INF and max_ind = -1

index of 1 is 2, so min_ind = min(min_ind, 2) = 2 and max_ind = max(max_ind, 2) = 2,
2-2+1 = 1 so we have a permutation of size 1

index of 2 is 0, so min_ind = min(min_ind, 0) = 0 and max_ind = max(max_ind, 0) = 2,
2-0+1 = 3 so we don’t have a permutation of size 2

index of 3 is 1, so min_ind = min(min_ind, 1) = 0 and max_ind = max(max_ind, 1) = 2,
2-0+1 = 3 so we have a permutation of size 3

index of 4 is 4, so min_ind = min(min_ind, 4) = 0 and max_ind = max(max_ind, 4) = 4,
4-0+1 = 5 so we don’t have a permutation of size 4

index of 5 is 3, so min_ind = min(min_ind, 3) = 0 and max_ind = max(max_ind, 4) = 4,
4-0+1 = 5 so we have a permutation of size 5

So answer is 3

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
int find_permutations(vector<int>& arr)
{
    int cnt = 0;
    int max_ind = -1, min_ind = 10000000;
    int n = arr.size();
    unordered_map<int, int> index_of;
 
    // Save index of numbers of the array
    for (int i = 0; i < n; i++) {
        index_of[arr[i]] = i + 1;
    }
 
    for (int i = 1; i <= n; i++) {
 
        // Update min and max index
        // with the current index
        // and check if it's a valid permutation
        max_ind = max(max_ind, index_of[i]);
        min_ind = min(min_ind, index_of[i]);
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(4);
 
    cout << find_permutations(nums);
 
    return 0;
}

Java

// Java program to implement 
// the above approach 
import java.util.*;
 
class GFG{
     
public static int find_permutations(
    Vector<Integer> arr) 
{ 
    int cnt = 0; 
    int max_ind = -1, min_ind = 10000000; 
    int n = arr.size(); 
     
    HashMap<Integer, 
            Integer> index_of = new HashMap<>(); 
             
    // Save index of numbers of the array 
    for(int i = 0; i < n; i++) 
    { 
        index_of.put(arr.get(i), i + 1);
    } 
 
    for(int i = 1; i <= n; i++) 
    { 
         
        // Update min and max index with 
        // the current index and check 
        // if it's a valid permutation 
        max_ind = Math.max(max_ind, index_of.get(i)); 
        min_ind = Math.min(min_ind, index_of.get(i)); 
         
        if (max_ind - min_ind + 1 == i) 
            cnt++; 
    } 
    return cnt; 
} 
 
// Driver Code
public static void main(String[] args)
{
    Vector<Integer> nums = new Vector<Integer>(); 
    nums.add(2); 
    nums.add(3); 
    nums.add(1); 
    nums.add(5); 
    nums.add(4); 
     
    System.out.print(find_permutations(nums));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program to implement
# the above approach
def find_permutations(arr):
     
    cnt = 0
    max_ind = -1
    min_ind = 10000000;
     
    n = len(arr)
    index_of = {}
 
    # Save index of numbers of the array
    for i in range(n):
        index_of[arr[i]] = i + 1
 
    for i in range(1, n + 1):
 
        # Update min and max index with the
        # current index and check if it's a
        # valid permutation
        max_ind = max(max_ind, index_of[i])
        min_ind = min(min_ind, index_of[i])
         
        if (max_ind - min_ind + 1 == i):
            cnt += 1
             
    return cnt
 
# Driver code
if __name__ == "__main__":
 
    nums = []
    nums.append(2)
    nums.append(3)
    nums.append(1)
    nums.append(5)
    nums.append(4)
 
    print(find_permutations(nums))
 
# This code is contributed by chitranayal

C#

// C# program to implement
// the above approach
using System; 
using System.Collections; 
using System.Collections.Generic; 
 
class GFG{
     
static int find_permutations(ArrayList arr)
{
    int cnt = 0;
    int max_ind = -1, min_ind = 10000000;
    int n = arr.Count;
     
    Dictionary<int, 
               int> index_of = new Dictionary<int,
                                              int>(); 
             
    // Save index of numbers of the array
    for(int i = 0; i < n; i++) 
    {
        index_of[(int)arr[i]] = i + 1;
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Update min and max index with 
        // the current index and check 
        // if it's a valid permutation
        max_ind = Math.Max(max_ind, index_of[i]);
        min_ind = Math.Min(min_ind, index_of[i]);
         
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
    return cnt;
}
 
// Driver Code
public static void Main(string[] args)
{
    ArrayList nums = new ArrayList(); 
 
    nums.Add(2);
    nums.Add(3);
    nums.Add(1);
    nums.Add(5);
    nums.Add(4);
 
    Console.Write(find_permutations(nums));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript implementation
function find_permutations(arr)
{
    var cnt = 0;
    var max_ind = -1, min_ind = 10000000;
    var n = arr.length;
    var index_of = new Map();
   
    // Save index of numbers of the array
    for (var i = 0; i < n; i++) {
        index_of.set(arr[i], i + 1);
    }
   
    for (var i = 1; i <= n; i++) {
   
        // Update min and max index
        // with the current index
        // and check if it's a valid permutation
        max_ind = Math.max(max_ind, index_of.get(i));
        min_ind = Math.min(min_ind, index_of.get(i));
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
   
    return cnt;
}
  
var nums = [];
nums.push(2);
nums.push(3);
nums.push(1);
nums.push(5);
nums.push(4);
 
document.write(find_permutations(nums));
// This code contributed by shubhamsingh10
</script>

Output:

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!