Im trying to write a class named Range, that takes "n" length array of integers (unsorted) so that the integers are from 0 to k (value).

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

Then I want to write a query function that takes two integers a and b, forms a range of numbers from a to b and returns the frequency of all the numbers that are between the range who are also located inside "n" length array(sorted).

My approach till now:

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 want that query will have O(1) time complexity.

So my question is: Is it possible to implement the method "query" via HashMap? if not, what are the alternatives and why? (Note: the time complexity should be O(1) for query, not bothering about the space complexity).

Edit: In main class:

int[] a = {13,12,13,1,2,0,0,1,3,4};
Range arr = new Range(a, 13);
System.out.print(arr);    // print 0,0,1,1,2,3,4,12,13,13

Then suppose a = 1 and b = 4 so that the range to be tested is 2,3,4. The output compared to the sorted array should be: 5 because of 1,1,2,3,4.

Kindly Regards

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.