fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fo(i,start,end) for(int i=start;i<end;i++)
  4. class Solution {
  5. public:
  6.     int minimumDistance(vector<int>& nums) {
  7.         /*Brute Force
  8.         Take 3 Pointers (i,j,k) 
  9.             for each i, move j and k to find 3 elements that are same
  10.             o(n^3) time complexity not feasible
  11.         */
  12.         // element -> {freq,lastSeenIndex(vector)}
  13.         // 1 -> {vector or instances}
  14.         //{1,2,1,1,3}
  15.         int n = nums.size();
  16.         int result = INT_MAX;
  17.         unordered_map<int,vector<int>>mp; //element -> freq
  18.         fo(it,0,n){
  19.             mp[nums[it]].push_back(it); //increment the frequency
  20.             if(mp[nums[it]].size() >= 3){
  21.               vector<int>& myValues = mp[nums[it]];
  22.                int s = myValues.size();
  23.                // Grab the 3 MOST RECENT indices (not always 0, 1, and 2)
  24.                int first = myValues[s - 3];
  25.                int second = myValues[s - 2];
  26.                int third = myValues[s - 1];
  27.                 result =   min(result,(abs(first-second) +  abs(second-third) + abs(third - first))); 
  28.             }
  29.  
  30.  
  31.         }
  32.         if(result == INT_MAX)  return -1;
  33.         else return result;
  34.  
  35.         //if nothing is found
  36.     }
  37. };
  38. int main(){
  39. 	vector<int>arr = {1,2,1,1,3};
  40. 	Solution s;
  41. 	int ans = s.minimumDistance(arr);
  42. 	cout<<ans<<endl;
  43.  
  44. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/OTMMCi
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!