Given a permutation of integers from 1 to N and an integer M, the task is to check if any subarray of the given permutation is a permutation of the integers from 1 to M.
Examples:
Input: arr[] = {4, 5, 1, 3, 2, 6}, M = 3
Output: Yes
{4, 5, 1, 3, 2, 6} is the required subarray.Input: arr[] = {4, 5, 1, 3, 2, 6}, M = 4
Output: No
Naive approach: A naive approach would be to generate all the M-sized subarrays and see if any such subarray exists. But if the given permutation is too large, this approach will be time-consuming as it runs in O(N3).
Efficient approach: A better solution is to use Hashing.
- From the main permutation, the positions of each integer are stored in a map/dictionary.
- Now, observe that if there exists a subarray which is a permutation from 1 to m, then all numbers in range [1, m] will occupy m consecutive places in the main permutation, either in a sorted or random manner.
- Their positions also should come as m-consecutive numbers, when sorted, starting with the minimum position/value x, and its m-1 consecutive positions.
- Therefore the ‘sum of positions’ for each integer 1 to n can be calculated, where sum_of_position(k) = sumcur= Position_of_1 + Position_of_2 + …Position_of_k.
- Let the minimum element of the above series be x. When the positions are sorted, this will be the first element and the rest will be consecutive.
- Then if the required subarray exists, then sum_of_position(m) has to be x + (x+1) + ..(x+m-1) {m consecutive terms} = x*m – m + m*(m+1)/2 .
- If sum of all positions for integers 1 to m is this sum, then for given m, true is returned, else there is no such sub-array.
Below is the implementation of the above approach.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;typedef long long int ll;// Function that returns true if the// required subarray exists// in the given arraybool subArray(ll* arr, ll n, ll m){ ll i; // Map to store the positions of // each integer in the original // permutation unordered_map<ll, ll> mp; for (i = 0; i < n; i++) { // To store the address of each // entry in arr[n] but with // 1-based indexing mp[arr[i]] = i + 1; } ll sumcur = 0; // To track minimum position sumcur // for sum of all positions // till this position ll p = INT_MAX; vector<ll> ans; for (i = 1; i <= m; i++) { // Summing up addresses sumcur += mp[i]; // Tracking minimum address // encountered till now p = min(p, mp[i]); // The sum of the addresses if // it forms the required subarray ll val = p * i - i + (i * (i + 1)) / 2; if (i == m) { // If current sum of address // is equal to val if (val == sumcur) { return true; } else return false; } }}// Driver codeint main(){ ll arr[] = { 4, 5, 1, 3, 2, 6 }; int n = sizeof(arr) / sizeof(int); ll m = 3; if (subArray(arr, n, m)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function that returns true if the// required subarray exists// in the given arraystatic boolean subArray(int[] arr, int n, int m){ int i; // Map to store the positions of // each integer in the original // permutation HashMap<Integer, Integer> mp = new HashMap<Integer, Integer> (); for (i = 0; i < n; i++) { // To store the address of each // entry in arr[n] but with // 1-based indexing mp.put(arr[i], i + 1); } int sumcur = 0; // To track minimum position sumcur // for sum of all positions // tiint this position int p = Integer.MAX_VALUE; Vector<Integer> ans = new Vector<Integer>(); for (i = 1; i <= m; i++) { // Summing up addresses sumcur += mp.get(i); // Tracking minimum address // encountered tiint now p = Math.min(p, mp.get(i)); // The sum of the addresses if // it forms the required subarray int val = p * i - i + (i * (i + 1)) / 2; if (i == m) { // If current sum of address // is equal to val if (val == sumcur) { return true; } else return false; } } return false;}// Driver codepublic static void main(String[] args){ int arr[] = { 4, 5, 1, 3, 2, 6 }; int n = arr.length; int m = 3; if (subArray(arr, n, m)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function that returns true if the# required subarray exists# in the given arraydef subArray(arr, n, m): i = 0 # Map to store the positions of # each integer in the original # permutation mp = dict() for i in range(n): # To store the address of each # entry in arr[n] but with # 1-based indexing mp[arr[i]] = i + 1 sumcur = 0 # To track minimum position sumcur # for sum of all positions # ti this position p = 10**9 ans = [] for i in range(1, m + 1): # Summing up addresses sumcur += mp[i] # Tracking minimum address # encountered ti now p = min(p, mp[i]) # The sum of the addresses if # it forms the required subarray val = p * i - i + (i * (i + 1)) / 2 if (i == m): # If current sum of address # is equal to val if (val == sumcur): return True else: return False# Driver codearr = [4, 5, 1, 3, 2, 6]n = len(arr)m = 3if (subArray(arr, n, m)): print("Yes")else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Function that returns true if the// required subarray exists// in the given arraystatic bool subArray(int[] arr, int n, int m){ int i; // Map to store the positions of // each integer in the original // permutation Dictionary<int, int> mp = new Dictionary<int, int> (); for (i = 0; i < n; i++) { // To store the address of each // entry in arr[n] but with // 1-based indexing mp.Add(arr[i], i + 1); } int sumcur = 0; // To track minimum position sumcur // for sum of all positions // tiint this position int p = int.MaxValue; List<int> ans = new List<int>(); for (i = 1; i <= m; i++) { // Summing up addresses sumcur += mp[i]; // Tracking minimum address // encountered tiint now p = Math.Min(p, mp[i]); // The sum of the addresses if // it forms the required subarray int val = p * i - i + (i * (i + 1)) / 2; if (i == m) { // If current sum of address // is equal to val if (val == sumcur) { return true; } else return false; } } return false;}// Driver codepublic static void Main(String[] args){ int []arr = { 4, 5, 1, 3, 2, 6 }; int n = arr.Length; int m = 3; if (subArray(arr, n, m)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if the// required subarray exists// in the given arrayfunction subArray(arr, n, m){ var i; // Map to store the positions of // each integer in the original // permutation var mp = new Map(); for(i = 0; i < n; i++) { // To store the address of each // entry in arr[n] but with // 1-based indexing mp.set(arr[i], i + 1); } var sumcur = 0; // To track minimum position sumcur // for sum of all positions // till this position var p = 1000000000; var ans = []; for(i = 1; i <= m; i++) { // Summing up addresses sumcur += mp.get(i); // Tracking minimum address // encountered till now p = Math.min(p, mp.get(i)); // The sum of the addresses if // it forms the required subarray var val = p * i - i + parseInt((i * (i + 1)) / 2); if (i == m) { // If current sum of address // is equal to val if (val == sumcur) { return true; } else return false; } }}// Driver codevar arr = [ 4, 5, 1, 3, 2, 6 ];var n = arr.length;var m = 3;if (subArray(arr, n, m)) document.write("Yes");else document.write("No"); // This code is contributed by famously</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N) because it is using extra space for map
Another Efficient Approach: Using Sliding Window
We will use a M sized sliding window in which we will keep a count of numbers less than or equal to M and iterate over the array. If the count becomes equal to M, we have found the permutation.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std; typedef long long int ll; // Function that returns true if the// required subarray exists// in the given arraybool subArray(ll* arr, ll n, ll m){ int count = 0;//count less than m for (int i = 0; i < m; i++){ if (arr[i] <= m) count++; } if (count == m) return true; for (int i = m; i < n; i++){ if (arr[i-m] <= m) count--; if (arr[i] <= m) count++; if (count == m) return true; } return false;} // Driver codeint main(){ ll arr[] = { 4, 5, 1, 3, 2, 6 }; int n = sizeof(arr) / sizeof(int); ll m = 3; if (subArray(arr, n, m)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function that returns true if the // required subarray exists // in the given array static boolean subArray(int[] arr, int n, int m) { int count = 0; // count less than m for (int i = 0; i < m; i++) { if (arr[i] <= m) count++; } if (count == m) return true; for (int i = m; i < n; i++) { if (arr[i - m] <= m) count--; if (arr[i] <= m) count++; if (count == m) return true; } return false; } // Driver code public static void main(String[] args) { int arr[] = { 4, 5, 1, 3, 2, 6 }; int n = arr.length; int m = 3; if (subArray(arr, n, m)) System.out.print("Yes"); else System.out.print("No"); }}// This code is contributed by subhammahato348. |
Python3
# Python3 implementation of the approach# Function that returns true if the# required subarray exists# in the given arraydef subArray(arr, n, m): count = 0 # count less than m for i in range(m): if (arr[i] <= m): count += 1 if (count == m): return True for i in range(m,n): if (arr[i-m] <= m): count -= 1 if (arr[i] <= m): count += 1 if (count == m): return True return False # Driver codearr = [ 4, 5, 1, 3, 2, 6 ]n = len(arr)m = 3 if (subArray(arr, n, m)): print("Yes")else: print("No") # This code is contributed by shinjanpatra |
C#
// C# implementation of the approachusing System;class GFG { // Function that returns true if the // required subarray exists // in the given array static bool subArray(int[] arr, int n, int m) { int count = 0; // count less than m for (int i = 0; i < m; i++) { if (arr[i] <= m) count++; } if (count == m) return true; for (int i = m; i < n; i++) { if (arr[i - m] <= m) count--; if (arr[i] <= m) count++; if (count == m) return true; } return false; } // Driver code public static void Main() { int[] arr = { 4, 5, 1, 3, 2, 6 }; int n = arr.Length; int m = 3; if (subArray(arr, n, m)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by subhammahato348. |
Javascript
<script>// JavaScript implementation of the approach// Function that returns true if the// required subarray exists// in the given arrayfunction subArray(arr, n, m){ let count = 0//count less than m for (let i = 0; i < m; i++){ if (arr[i] <= m) count++; } if (count == m) return true; for (let i = m; i < n; i++){ if (arr[i-m] <= m) count--; if (arr[i] <= m) count++; if (count == m) return true; } return false;} // Driver codelet arr =[ 4, 5, 1, 3, 2, 6 ]let n = arr.lengthlet m = 3 if (subArray(arr, n, m)) document.write("Yes")else document.write("No")// This code is contributed by shinjanpatra</script> |
Time Complexity: O(N)
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!
