Coding Challenge Solution – Find Num of Elements in a range in O(1) with preprocessing

This is my solution to the following Coding Challenge – Find Num of Elements in a Range in O(1) with Preprocessing

given array and max element in array. Find no. of elements present between a given range in O(1). You can do one time processing of array. 


#include <iostream> #include <vector> #include <unordered_map> #include <algorithm> using namespace std;  class Solution  {     public:      Solution(vector<int>& v)      {         sort(v.begin(), v.end());           for(unsigned int i=0; i<v.size(); ++i) m[v[i]] = i;      }      unsigned int count(const int a, const int b)     {                if(!(a < b)) throw runtime_error("Wrong Order");          if( (m.find(a) == m.end()) || (m.find(b) == m.end()) ) throw runtime_error("Not Found");          return m[b] - m[a] + 1;      }      private:      unordered_map<int, unsigned int> m;  };   int main() {     // your code goes here     int N;      cin >> N;      vector<int> data;      for(int i=0; i<N; ++i)      {         int temp;          cin >> temp;          data.push_back(temp);      }      Solution sol(data);      const auto left = 1;      const auto right = 3;      const auto res = sol.count(left, right);      cout << "Left = " << left << ", Right = " << right << " --> Res = " << res << endl;      return 0; }  

Notes – Even if typically for Algorithmic Coding Challenges a free function is good enough and using a class is over-engineering, in this specific I went for the class on purpose in order to possibly amortize the pre-processing cost by multiple calls to the count() method