CODEWITHSUNDEEP
javaalgorithm
tester mi
tester mi

Reputation: 23

Algorithm performance. I can't solve it

I'm trying to solve an algorithm problem, but I think my resolution is not good in performance. So if someone could help I will be very grateful.

The problem is: I have 3 arrays A,B,C. I want to know how many elements are within range of each B[i] and C[i]. 

Example:
A = [1,3,5,8]
B = [3,8]
C= [7,8]

So for B[0] and C[0] the answer is 2, because 3 and 5 are within range
and for B[1] and C[1] the answer is 1, because 8 are within range

the result has to be an array of [2,1].

Specifications:
B.length == C.length
B[i] <= C[i]

I tried my to solve this problem that way:

static int[] method(int[] A, int[] B, int[] C) {
    Arrays.sort(A);
    int[] result = new int[B.length];
    for (int i = 0; i < B.length; i++) {
        int x = B[i];
        int y = C[i];
        int init = -1;
        int end = -1;
        for (int j = 0; j < A.length; j++) {
            int a = A[j];
            if (a >= x && init == -1) {
                init = j;
            }
            if (a == y && end == -1) {
                end = j;
            }
            if (a > y && end == -1) {
                end = j - 1;
            }
            if (init != -1 && end != -1) {
                break;
            }
        }
        result[i] = end - init + 1;
    }
    return result;
}

What do you guys think?

Upvotes: 2

Views: 151

Answers (5)

TrapII
TrapII

Reputation: 2275

To add something to the answer from Henry, when there are a lot of numbers, the binary search algorithm is by far the best. Also it seems that your solution doesn't take into account duplicate values in A.

A fully functional code :

static int[] method2(int[] A, int[] B, int[] C) {
    Arrays.sort(A);
    int[] result = new int[B.length];
    for (int i = 0; i < B.length; i++) {
        int posMin = java.util.Arrays.binarySearch(A, B[i]);
        int posMax = java.util.Arrays.binarySearch(A, C[i]);
        if (posMin < 0) { posMin = -(posMin+1);   }
        if (posMax < 0) { posMax = -(posMax+1)-1; }
        result[i] = posMax - posMin +1;
    }
    return result;
}

From the tests I have done with 100 intervals and 1 million sample.

method = 16368ms

method2 = 433ms

Upvotes: 0

Henry
Henry

Reputation: 43728

The best procedure depends on the sizes of A and B.

If A is very large compared to B, it is better not to sort it. Run through all elements of A and for each one check all intervals if they contain the element. This gives a runtime of O(len A * len B)

On the other hand if there are many intervals, it is better to sort A and to use binary search to find the start and end index for each interval. This gives a runtime of O(len A * log(len A) + len B * log(len A)).

Upvotes: 1

Mr. Mak
Mr. Mak

Reputation: 867

Here you go with java8

public static int[] doTask(int[] A, int[] B, int[] C) {
    // Arrays.sort(A);

    List<Integer> aList = Arrays.stream(A).boxed().collect(Collectors.toList());

    int result[]=new int[B.length];
    for (int i=0; i < B.length; i++) {
        Integer b = B[i];
        Integer c = C[i];
        List<Integer> aList2 = aList.stream().filter(a -> a >= b && a <= c).collect(Collectors.toList());
        result[i] = aList2.size();
    }

    // System.out.println(result);
    return result;
}

result = [2, 1]

Upvotes: 0

arizafar
arizafar

Reputation: 3122

1) Concatenate the array A with B[i] & C[i]. i.e
   new array will be [1,3,5,8,3,7]
2) Sort the new array.
   sorted array [1,3,3,5,7,8]
3) filter out the elements between B[i] & C[i] from the array.
   filtered array [3,3,5,7]

Upvotes: 0

Bryan Patterson
Bryan Patterson

Reputation: 64

You could just increment result[i] on the fly as you're running through the B and C arrays.

static int[] method(int[] A, int[] B, int[] C)
{
    Arrays.sort(A);
    int[] result = new int[B.length];
    for (int i = 0; i < B.length; i++)
    {
        for (int j = 0; j < A.length; j++)
        {
            int a = A[j];
            if (B[i] <= a && a <= C[i])
            {
                result[i]++;
            }
            else if (a >= C[i])
            {
                break;
            }
        }
    }
    return result;
}

Upvotes: 0

Related Questions