Data Structure

Given an unsorted array of n integers numbers (with possible duplicates) in range [1..k]. Implement in Java an algorithm that preprocesses the input array in O(n+k) running time and then returns how many integer numbers there are in the range [left..right] in O(1) running time for any given left and right, 1 < = left < = right < =k.

Example:

Input: int [ ] a = {3, 8, 2, 4, 1, 9, 11, 4, 15}; //input array

int k = 15; // max element in a

int left = 2; // lower value in range

int right = 9; // upper value in range

Output:

Total number in range [2..9] is 6