Check for each subarray whether it consists of all natural numbers up to its length or not
Given an array, arr[] representing a permutation of first N natural numbers in the range [1, N], the task for each ith index is to check if an i-length subarray exists or not such that it contains all the numbers in the range [1, i].
Note: 1 – based indexing used.
Examples:
Input: arr[] = {4, 5, 1, 3, 2}
Output: True False True False True
Explanation:
For i = 1, the subarray {arr[2]} contains all the numbers from [1, i] and of size i(=1). Therefore, the required output is true.
For i = 2, no subarray of size 2 exists which contains all the numbers in the range[1, i]. Therefore, the required output is false.
For i = 3, the subarray {arr[2], arr[3], arr[4]} contains all the numbers from [1, i] and of size i(=3). Therefore, the required output is true.
For i = 4, no subarray of size 4 exists which contains all the numbers in the range[1, i]. Therefore, the required output is false.
For i = 5, the subarray {arr[0], arr[1], arr[2], arr[3], arr[4]} contains all the numbers from [1, i] and of size i(=5). Therefore, the required output is true.Input: arr = {1, 4, 3, 2}
Output: True False False True
Naive Approach: The idea is to traverse the array and for each index, check if there is a subarray of size i which contains all the numbers in the range [1, i] or not. If found to be true, then print True. Otherwise, print False.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The problem can be solved using Hashing to store the position of each element of the given array efficiently. Follow the steps below to solve the problem:
- Create a map, say, Map, to store the position of each element of the given array.
- Traverse the array and store the position of each element of the array onto Map.
- Create a set, say st to store the indexes of each element from the range [1, N].
- Initialize two variables, say Min and Max, to store the smallest and the largest elements present in st.
- Iterate over the range [1, N] and insert the value of Map[i] into st and check if Max – Min + 1 = i or not. If found to be true, then print True.
- Otherwise, print False.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] void checksubarrayExist1_N( int arr[], int N) { // Store the position // of each element of arr[] unordered_map< int , int > pos; // Traverse the array for ( int i = 0; i < N; i++) { // Insert the position // of arr[i] pos[arr[i]] = i; } // Store position of each element // from the range [1, N] set< int > st; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // Insert the index of i into st st.insert(pos[i]); // Find the smallest element of st int Min = *(st.begin()); // Find the largest element of st int Max = *(st.rbegin()); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { cout << "True " ; } else { cout << "False " ; } } } // Driver Code int main() { int arr[] = { 1, 4, 3, 2 }; int N = sizeof (arr) / sizeof (arr[0]); checksubarrayExist1_N(arr, N); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] static void checksubarrayExist1_N( int arr[], int N) { // Store the position // of each element of arr[] Map<Integer, Integer> pos= new HashMap<>(); // Traverse the array for ( int i = 0 ; i < N; i++) { // Insert the position // of arr[i] pos.put(arr[i],i); } // Store position of each element // from the range [1, N] Set<Integer> st= new HashSet<>(); // Iterate over the range [1, N] for ( int i = 1 ; i <= N; i++) { // Insert the index of i into st st.add(pos.get(i)); // Find the smallest element of st int Min = Collections.min(st); // Find the largest element of st int Max = Collections.max(st); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { System.out.print( "True " ); } else { System.out.print( "False " ); } } } // Driver code public static void main(String[] args) { int arr[] = { 1 , 4 , 3 , 2 }; int N = arr.length; checksubarrayExist1_N(arr, N); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to check if a subarray of size i exists # that contain all the numbers in the range [1, i] def checksubarrayExist1_N(arr, N): # Store the position # of each element of arr[] pos = {} # Traverse the array for i in range (N): # Insert the position # of arr[i] pos[arr[i]] = i # Store position of each element # from the range [1, N] st = {} # Iterate over the range [1, N] for i in range ( 1 , N + 1 ): # Insert the index of i into st st[pos[i]] = 1 # Find the smallest element of st Min = sorted ( list (st.keys()))[ 0 ] # Find the largest element of st Max = sorted ( list (st.keys()))[ - 1 ] # If distance between the largest # and smallest element of arr[] # till i-th index is equal to i if ( Max - Min + 1 = = i): print ( "True" , end = " " ) else : print ( "False" , end = " " ) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 4 , 3 , 2 ] N = len (arr) checksubarrayExist1_N(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; using System.Linq; class GFG{ // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] static void checksubarrayExist1_N( int [] arr, int N) { // Store the position // of each element of arr[] Dictionary< int , int > pos = new Dictionary< int , int >(); // Traverse the array for ( int i = 0; i < N; i++) { // Insert the position // of arr[i] pos[arr[i]] = i; } // Store position of each element // from the range [1, N] HashSet< int > st = new HashSet< int >(); // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { // Insert the index of i into st st.Add(pos[i]); // Find the smallest element of st int Min = st.Min(); // Find the largest element of st int Max = st.Max(); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { Console.Write( "True " ); } else { Console.Write( "False " ); } } } // Driver code public static void Main( string [] args) { int [] arr = { 1, 4, 3, 2 }; int N = arr.Length; checksubarrayExist1_N(arr, N); } } // This code is contributed by ukasp |
Javascript
<script> // JavaScript program for the above approach // Function to check if a subarray of size i exists // that contain all the numbers in the range [1, i] function checksubarrayExist1_N(arr, N) { // Store the position // of each element of arr[] let pos = new Map(); // Traverse the array for (let i = 0; i < N; i++) { // Insert the position // of arr[i] pos.set(arr[i],i); } // Store position of each element // from the range [1, N] let st= new Set(); // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { // Insert the index of i into st st.add(pos.get(i)); // Find the smallest element of st let Min = Math.min(...st); // Find the largest element of st let Max = Math.max(...st); // If distance between the largest // and smallest element of arr[] // till i-th index is equal to i if (Max - Min + 1 == i) { document.write( "True " ); } else { document.write( "False " ); } } } // Driver Code let arr = [ 1, 4, 3, 2 ]; let N = arr.length; checksubarrayExist1_N(arr, N); </script> |
True False False True
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)