Minimum length subarray containing all unique elements after Q operations | C ++ implementation to find the minimum size subarray containing all unique elements after processing the array for K queries of ranges ; Function to find minimum size subarray of all array elements ; Updating the array after processing each query ; Making it to 0 - indexing ; Prefix sum array concept is used to obtain the count array ; Iterating over the array to get the final array ; Variable to get count of all unique elements ; Hash to maintain perviously occurred elements ; Loop to find the all unique elements ; array to maintain counter of encountered elements ; variable to store answer ; Using two pointers approach ; Increment counter if occurred once ; when all unique elements are found ; update answer with minimum size ; decrement count of elements from left ; decrement counter ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int subarrayLength ( int A [ ] , int R [ ] [ 2 ] , int N , int M ) { for ( int i = 0 ; i < M ; ++ i ) { int l = R [ i ] [ 0 ] , r = R [ i ] [ 1 ] + 1 ; l -- ; r -- ; A [ l ] ++ ; if ( r < N ) A [ r ] -- ; } for ( int i = 1 ; i < N ; ++ i ) { A [ i ] += A [ i - 1 ] ; } int count = 0 ; unordered_set < int > s ; for ( int i = 0 ; i < N ; ++ i ) { if ( s . find ( A [ i ] ) == s . end ( ) ) count ++ ; s . insert ( A [ i ] ) ; } vector < int > repeat ( count + 1 , 0 ) ; int ans = N ; int counter = 0 , left = 0 , right = 0 ; while ( right < N ) { int cur_element = A [ right ] ; repeat [ cur_element ] += 1 ; if ( repeat [ cur_element ] == 1 ) ++ counter ; while ( counter == count ) { ans = min ( ans , right - left + 1 ) ; cur_element = A [ left ] ; repeat [ cur_element ] -= 1 ; ++ left ; if ( repeat [ cur_element ] == 0 ) -- counter ; } ++ right ; } return ans ; } int main ( ) { int N = 8 , queries = 6 ; int Q [ ] [ 2 ] = { { 1 , 4 } , { 3 , 4 } , { 4 , 5 } , { 5 , 5 } , { 7 , 8 } , { 8 , 8 } } ; int A [ N ] = { 0 } ; cout << subarrayLength ( A , Q , N , queries ) ; return 0 ; }