Smallest element present in every subarray of all possible lengths | C ++ program for the above approach ; Function to add count of numbers in the map for a subarray of length k ; Set to store unique elements ; Add elements to the set ; Iterator of the set ; Adding count in map ; Function to check if there is any number which repeats itself in every subarray of length K ; Check all number starting from 1 ; Check if i occurred n - k + 1 times ; Print the smallest number ; Print - 1 , if no such number found ; Function to count frequency of each number in each subarray of length K ; Traverse all subarrays of length K ; Check and print the smallest number present in every subarray and print it ; Function to generate the value of K ; Function call ; Driver Code ; Given array ; Size of array ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void uniqueElements ( int arr [ ] , int start , int K , map < int , int > & mp ) { set < int > st ; for ( int i = 0 ; i < K ; i ++ ) st . insert ( arr [ start + i ] ) ; set < int > :: iterator itr = st . begin ( ) ; for ( ; itr != st . end ( ) ; itr ++ ) mp [ * itr ] ++ ; } void checkAnswer ( map < int , int > & mp , int N , int K ) { for ( int i = 1 ; i <= N ; i ++ ) { if ( mp [ i ] == ( N - K + 1 ) ) { cout << i << " ▁ " ; return ; } } cout << -1 << " ▁ " ; } void smallestPresentNumber ( int arr [ ] , int N , int K ) { map < int , int > mp ; for ( int i = 0 ; i <= N - K ; i ++ ) { uniqueElements ( arr , i , K , mp ) ; } checkAnswer ( mp , N , K ) ; } void generateK ( int arr [ ] , int N ) { for ( int k = 1 ; k <= N ; k ++ ) smallestPresentNumber ( arr , N , k ) ; } int main ( ) { int arr [ ] = { 2 , 3 , 5 , 3 , 2 , 3 , 1 , 3 , 2 , 7 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; generateK ( arr , N ) ; return ( 0 ) ; }