Overview

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

Given an array and max element in the array, find the number of elements present between a given range in $$\O(1)\$$. You can do one-time processing of an array.

Solutions

Solution1

#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;
}

Input

10
1 3 5 7 9 6 2 8 12 22

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.

Solution2

This is an Edit in order to propose an alternative solution based on @peter-taylor comment about the range

This solution does not throw an exception in case the values in the input range are not in the array and it is still $O(1)$ in time, just added more space complexity

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution
{
public:
Solution(vector<int>& v)
{
sort(v.begin(), v.end());
start = v;
end = v[v.size()-1];

unsigned int count=1;
unsigned int j=1;

for(int i=start; i<end; ++i)
{
if(i==v[j])
{
count++;
j++;
}

m[i] = count;
}
}

unsigned int count(const int a, const int b)
{
if(!(a < b)) throw runtime_error("Wrong Order");
return get_num(b) - get_num(a);
}

private:
unordered_map<int, unsigned int> m;
int start;
int end;

unsigned int get_num(const int a)
{
if(a < start) return 0 ;
if(a >= end) return m.size();
return m[a];
}
};

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 = 0;
const auto right = 3;
const auto res = sol.count(left, right);
cout << "Left = " << left << ", Right = " << right << " --> Res = " << res << endl;
return 0;
}

Notes

• In this implementation the number of elements is computed in a (a,b] range (so first not counted) as this is not violating anything in the specs
• This looks obviously buggy to me - the spec says nothing to justify the throw. What test cases did you use to test it? – Peter Taylor May 31 at 7:17
• Why buggy? As the specs do not specify that case it's undefined behaviour (and I managed it in a reasonable way). It does not make sense to test undefined behaviours in test cases – Nicola Bernini May 31 at 18:15
• The spec says "a given range". It's not reasonable to say that since it doesn't explicitly say "a given range whose endpoints might not be in the array" it must mean "a given range whose endpoints are in the array". – Peter Taylor May 31 at 19:51
• OK @PeterTaylor I have added Solution 2 according to your observation: still O(1) in time but more space complexity – Nicola Bernini Jun 1 at 7:02