Longest contiguous distinct subarray
This problem was asked by Google.
Given an array of elements, return the length of the longest subarray where all its elements are distinct.
For example, given the array [5, 1, 3, 5, 2, 3, 4, 1], return 5 as the longest subarray of distinct elements is [5, 2, 3, 4, 1].
My Solution(C++):
#include <iostream>
#include <vector>
#include <unordered_map>
int longestDistinctSubarray(std::vector<int> v){
int maxL = 0, cur;
int startLongest = 0; //starting index of the longest distinct subarray
std::unordered_map<int, int> H;
for (int i=0; i<v.size(); i++){
if (H.find(v[i])!=H.end()){
startLongest = H[v[i]]+1;
cur = i-startLongest;
maxL = (cur>maxL)?cur:maxL;
}
H[v[i]] = i;
}
return maxL;
}
void test(){
std::vector<int> A {5, 1, 3, 5, 2, 3, 4, 1};
int maxL = longestDistinctSubarray(A);
std::cout<<maxL<<'\n';
}
int main(){
test();
return 0;
}