Created
March 15, 2021 23:10
-
-
Save Abiwax/9b5c7dc1d1b7b7fd3fba60e4aebdc6fc to your computer and use it in GitHub Desktop.
sample code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<bits/stdc++.h> | |
using namespace std; | |
// please not at any time we will keep elements in the map called mp whose index lie between i to j. | |
// Initially both are 0 so only first element is added in the map | |
int solution(int a[], int n) | |
{ | |
set<int> st; // to store all the elements to find number of unique elements | |
for(int i = 0; i < n; i++){ | |
st.insert(a[i]); | |
} | |
int len = st.size(); // length of unique elements | |
map<int, int> mp; // map to store key as elements and values as their frequency | |
mp[a[0]] = 1; | |
int ans = n; // initial answer will be number of elements | |
for(int i = 0, j = 0; i < n && j < n;){ | |
if(mp.size() == len){ // if we have at least spanned through len elements | |
ans = min(ans, j - i + 1); // update the answer to minimum of current answer and length of span, | |
// elements are spanned from (i - j) index | |
if(mp[a[i]] == 1){ // if single entry | |
mp.erase(a[i]); // delete it | |
} | |
else{ | |
mp[a[i]]--; // increase the frequency | |
} | |
i++; | |
} | |
else if(mp.size() < len){ // if we have still not collected at least len elements | |
if(j < n-1){ // if there is score of collection | |
j++; | |
mp[a[j]]++; // include it | |
} | |
else{ // we have reached last element and need to break the loop | |
break; | |
} | |
} | |
if(mp.size() == len){ // update answer here too | |
ans = min(ans, j - i + 1); | |
} | |
} | |
return ans; // returns answer | |
} | |
int main() { | |
int a[] = {7, 5, 2, 7, 2, 7, 4, 7}; | |
int n = sizeof(a) / sizeof(a[0]); | |
cout << "Array: "; | |
for(int i = 0; i < n; i++){ | |
cout << a[i] << " "; | |
} | |
cout << endl; | |
cout << "Answer: " << solution(a, n); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment