Smallest element present in every subarray of all possible lengths | C ++ program of the above approach ; Function to print the common elements for all subarray lengths ; Function to find and store the minimum element present in all subarrays of all lengths from 1 to n ; Skip lengths for which answer [ i ] is - 1 ; Initialize minimum as the first element where answer [ i ] is not - 1 ; Updating the answer array ; If answer [ i ] is - 1 , then minimum can be substituted in that place ; Find minimum answer ; Function to find the minimum number corresponding to every subarray of length K , for every K from 1 to N ; Stores the minimum common elements for all subarray lengths ; Initialize with - 1. ; Find for every element , the minimum length such that the number is present in every subsequence of that particular length or more ; To store first occurence and gaps between occurences ; To cover the distance between last occurence and the end of the array ; To find the distance between any two occurences ; Update and store the answer ; Print the required answer ; Function to find the smallest element common in all subarrays for every possible subarray lengths ; Initializing indices array ; Store the numbers present in the array ; Push the index in the indices [ A [ i ] ] and also store the numbers in set to get the numbers present in input array ; Function call to calculate length of subarray for which a number is present in every subarray of that length ; Driver Code ; Given array ; Size of array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printAnswer ( int answer [ ] , int N ) { for ( int i = 1 ; i <= N ; i ++ ) { cout << answer [ i ] << " ▁ " ; } } void updateAnswerArray ( int answer [ ] , int N ) { int i = 0 ; while ( answer [ i ] == -1 ) i ++ ; int minimum = answer [ i ] ; while ( i <= N ) { if ( answer [ i ] == -1 ) answer [ i ] = minimum ; else answer [ i ] = min ( minimum , answer [ i ] ) ; minimum = min ( minimum , answer [ i ] ) ; i ++ ; } } void lengthOfSubarray ( vector < int > indices [ ] , set < int > st , int N ) { int answer [ N + 1 ] ; memset ( answer , -1 , sizeof ( answer ) ) ; for ( auto itr : st ) { int start = -1 ; int gap = -1 ; indices [ itr ] . push_back ( N ) ; for ( int i = 0 ; i < indices [ itr ] . size ( ) ; i ++ ) { gap = max ( gap , indices [ itr ] [ i ] - start ) ; start = indices [ itr ] [ i ] ; } if ( answer [ gap ] == -1 ) answer [ gap ] = itr ; } updateAnswerArray ( answer , N ) ; printAnswer ( answer , N ) ; } void smallestPresentNumber ( int arr [ ] , int N ) { vector < int > indices [ N + 1 ] ; set < int > elements ; for ( int i = 0 ; i < N ; i ++ ) { indices [ arr [ i ] ] . push_back ( i ) ; elements . insert ( arr [ i ] ) ; } lengthOfSubarray ( indices , elements , N ) ; } int main ( ) { int arr [ ] = { 2 , 3 , 5 , 3 , 2 , 3 , 1 , 3 , 2 , 7 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; smallestPresentNumber ( arr , N ) ; return ( 0 ) ; }