2

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?

Improve this question
7
  • 1
    It is not clear what is meant by "range" of B[i] and C[i]. What is range of B[i] alone? Do we have to consider the "range" of B and C simultaneously? Does your solution work but is slow? Commented Feb 26, 2018 at 4:41
  • Will the length of B and C array always be same, because if that's not the case then it might not work Commented Feb 26, 2018 at 4:47
  • Also is ur solution slow ? Time complexity of ur algorithm is O(n^2). Commented Feb 26, 2018 at 4:48
  • I think the general idea is return an int[] where result[i] = A.countElementsBetweenRange(B[i], C[i]); Commented Feb 26, 2018 at 4:51
  • 2
    Are the arrays A, B and C already in sorted order? Commented Feb 26, 2018 at 5:02

5 Answers 5

Reset to default
1

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)).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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

Improve this answer

1 Comment

Wow, I didn't saw your answer. Maybe this is the best way. I'll try it later and then I post here. Thanks
0

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;
}
Improve this answer

Comments

0 
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]
Improve this answer

4 Comments

So you sort A for each interval? Not efficient at all.
if we want for each ranges concat all arrays at once and then sort the new array.
How would you make sure then that you don't count the borders of other intervals as array elements?
ohh my bad. ----
0

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]

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.