title: Finding the number of elements between i and j in an integer array in o(1)
body: <p>Given an unsorted integer array and 2 numbers i and j such that 0 &lt;= i &lt;= j &lt;= C(a constant say MAX_INTEGER) what kind of pre-processing can be performed on it so that you will be able to find the number of numbers between i and j(both inclusive) in o(1) time. The array can also have duplicates.</p>
  
  <p>I had thought of building a frequency array f[] for the elements in the array(space o(C)) and also
  another array cf[] for cumulative frequency(space o(C)).</p>
  
  <p>So given i and j, i can look up the cumulative frequency array and do cf[j] - cf[i] - This will give the number of elements between i and j. To include i and j, look up the frequency array and add the values. ie cf[j] - cf[i] + f[i]+f[j]
  Time complexity will be o(1) * 4 = constant time.</p>
  
  <p>The look up in the frequency array can be avoided by finding the previous non zero cf array element for both i and j in the respective direction. This will increase the time complexity but will reduce the space complexity.</p>
  
  <p>Wanted to know if there is a better solution for this problem.</p>
  
  <p>Note - Values of i and j will be available to you only after the pre-processing is completed.</p>
  
  <p>-Vijay</p>