Check for each subarray whether it consists of all natural numbers up to its length or not | C ++ 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 ] ; Store the position of each element of arr [ ] ; Traverse the array ; Insert the position of arr [ i ] ; Store position of each element from the range [ 1 , N ] ; Iterate over the range [ 1 , N ] ; Insert the index of i into st ; Find the smallest element of st ; Find the largest element of st ; If distance between the largest and smallest element of arr [ ] till i - th index is equal to i ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void checksubarrayExist1_N ( int arr [ ] , int N ) { unordered_map < int , int > pos ; for ( int i = 0 ; i < N ; i ++ ) { pos [ arr [ i ] ] = i ; } set < int > st ; for ( int i = 1 ; i <= N ; i ++ ) { st . insert ( pos [ i ] ) ; int Min = * ( st . begin ( ) ) ; int Max = * ( st . rbegin ( ) ) ; if ( Max - Min + 1 == i ) { cout << " True ▁ " ; } else { cout << " False ▁ " ; } } } int main ( ) { int arr [ ] = { 1 , 4 , 3 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; checksubarrayExist1_N ( arr , N ) ; }