I'm trying to write a class named Range, that takes an array of integers (unsorted) of length n, containing only numbers in the range are from 0 to k.

At first, I declare a constructor which will preprocess the array via Counting Sort algorithm.

Then I want to write query() method that takes two integer arguments: a and b, which form a range of numbers from a to b and returns the total frequency of all the elements in the array having the values within the given range.

My code:

import java.util.Arrays;
import java.util.HashMap;

public class Range {

    private int[] a;
    private int k;

    public Range(int[] a, int k) {
        int index = 0;
        int[] counterArray = new int[k   1];

        for (int i : a)
            counterArray[i]  ;  // initialize counterArray

        for (int i = 0; i < counterArray.length; i  )
            while (0 < counterArray[i]) {
                a[index  ] = i;
                counterArray[i]--;
            }   // end while()

        this.a = a;
        this.k = k;
    }   // end constructor()

    public int query(int a, int b) {
        HashMap<Integer, Integer> map = new HashMap<>(a);

    }   // end query()

    @Override
    public String toString() {
        return Arrays.toString(a);
    }   // end toString()
}

I chose HashMap data structure because I need query() method to be executed in constant time O(1).

So my question is: Is it possible to implement the method query() via HashMap?

If not, what are the alternatives? (Note: the time complexity should be O(1) for query(), not bothering about the space complexity).

Code in the main() :

int[] a = {13,12,13,1,2,0,0,1,3,4};
Range range = new Range(a, 13);
System.out.print(range); // prints [0,0,1,1,2,3,4,12,13,13] because array has been sorted

System.out.print(range.query(1, 4)); // calculating number of elements in the range [1, 4]

Expected Output:

5   // elements 1,1,2,3,4 are within the range [1, 4]

Explanation: provided arguments of the query() are: a=1 and b=4, hence, values to be tested are 1,2,3,4. The output should be 5 because there are 5 elements: 1,1,2,3,4.

CodePudding user response：

To obtain the number of elements in the given range (from a to b inclusive) in O(1) time after the array has been sorted, you don't need to use HashMap. Instead, you can reuse the countingArray by making it an instance variable.

This approach also requires a slight modification of the sorting in order to retain the values in the countingArray intact. It's done by introducing one additional variable.

Note that it's a good practice to avoid mutating the input, that why in the code I've used Arrays.copyOf() (you can remove it, if you consider it irrelevant for this exercise).

I've extracted the logic responsible for sorting from the constructor into a separate method. And introduced a method which is meant to calculate the cumulative count for every number in the array (i.e. a number of element having values from 0 up to the current number inclusive).

So, after invoking method init() on the instance of Range we would be able to find the number of elements in the range from a to b by looking at the values stored in the countingArray at corresponding indices. And that would have a cost O(1).

public class Range {
    private int[] arr;
    private int[] counterArray;
    private int k;
    
    private Range(int[] arr, int k) { // constructor is not exposed
        this.arr = Arrays.copyOf(arr, arr.length);
        this.counterArray = new int[k   1];
        this.k = k;
    }
    
    public static Range getInstance(int[] arr, int k) {
        Range range = new Range(arr, k);
        range.init();
        return range;
    }
    
    private void init() {
        sort();
        sumUpCount();
    }
    
    private void sort() {

        for (int i : arr) {
            counterArray[i]  ;
        }

        int index = 0;
        int copy;
        for (int i = 0; i < counterArray.length; i  ) {
            copy = counterArray[i];
            while (0 < counterArray[i]) {
                arr[index  ] = i;
                counterArray[i]--;
            }
            counterArray[i] = copy;
        }
    }
    
    private void sumUpCount() {
        for (int i = 1; i < counterArray.length; i  ) {
            counterArray[i]  = counterArray[i - 1];
        }
    }
    
    public int query(int a, int b) {
        
        return a == 0 ? counterArray[b] :  counterArray[b] - counterArray[a - 1];
    }
}

main()

public static void main(String[] args) {
    int[] a = {13,12,13,1,2,0,0,1,3,4};
    Range range = Range.getInstance(a, 13);
    System.out.print(range.query(1,4));
}

Output:

5

CodePudding user response：

Yes, in order to cache/precompute the return values of query(), you need to create a composite key, that holds both values. The easiest way to do that is to use a string that holds both numbers divided by a separator. Separator is important otherwise composite key(21, 5) = "215" and key(2, 15) = "215". With separator that would be "21;5" and "2;15" respectivly.

private String key(int a, int b) {
    return String.format("%d;%d", a, b);
}

Then for each composite key possible you put the value into HashMap. In the query(a, b) method you just get the value from the Map.

public query(int a, int b) {
    return map.get(key(a, b));
}

The downside of this approach is that creation of this object is pretty expensive.