Finding if the element exist in a given range

Question

I have two arrays A and B. And I have to find the number of elements required by array C to fit into a specific length.

Length = B[i]-A[i]

For example:

A[0] = 1    B[0] = 4
A[1] = 4    B[1] = 5
A[2] = 5    B[2] = 9
A[3] = 8    B[3] = 10
and 
C[0] = 4
C[1] = 6
C[2] = 7
C[3] = 10
C[4] = 2

Answer would be 4.

Explanation:

C[0] is falling in the range of (A[0],B[0]) and (A[1],B[1])
C[1] is falling in the range of (A[2],B[2]) 
C[2] is of no use
C[3] is falling in the range of (A[3],B[3])
so the total is 4

My approaches:
Traditional approach: Simple looping every element of C in array A and if find in the range set the value of A[i] and B[i] to minus infinity or remove them(for Arraylist).

• Time complexity is an issue so not a good approach.

HashTable: Storing the value in hash table as A[i] as key and B[i] as value. Then finding the element for a given C[i] and removing the key. I think it is not a good approach

Please provide me a efficient algorithm for this.

Answer 1

I experimented with some tree structures but eventually I went back to a simple binary search, so this is now O(nlogn):

static int getAnswerV2a(int[] A, int[] B, int[] C) {
    int len = A.length;
    ArrayList<Interval> intervals = new ArrayList<Interval>(len);
    for (int i=0; i<len; i++) {
        intervals.add(new Interval(A[i], B[i]));
    }

    for (int i = 0; i < C.length; i++) {
        int c = C[i];
        binarySearch(intervals, 0, intervals.size(), c);
        if (intervals.isEmpty()) return i+1;
    }
    return -1;
}

static class Interval {
    int start, end;

    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }

    boolean matches(int c) {
        return start <= c && c <= end;
    }
}

// Find an interval (between indices i and j) that matches c
// When found, remove it from the List and adjust indices accordingly
static void binarySearch(ArrayList<Interval> intervals, int i, int j, int c) {
    if (i==j)
        return;
    else if (i+1==j) {
        if (intervals.get(i).matches(c))
            intervals.remove(i);
    }
    else {
        int mid = (int) Math.floor((i+j) / 2);
        Interval interval = intervals.get(mid);
        if (interval.start > c)
            binarySearch(intervals, i, mid, c);
        else if (interval.end < c)
            binarySearch(intervals, mid+1, j, c);
        else {
            intervals.remove(mid);
            binarySearch(intervals, i, j-1, c);
        }
    }
}

Answer 2

for(int i =0 ;i<C.length;i++)
for(int j=0;j<A.length;j++)
{
    if(A[i]<=C[i] && B[i]>=C[i])
   {   answer++;
       A[i] = Integer.Max_Value;
     }
}

It will give you a right answer

Answer 3

Here is one quick sketch for solving it in O(n log n). It may be not the best approach in practice, but is just meant to offer an n log n approach.

To summarize, it's a sweeping line technique. Or rather sweeping point, in this case.

1. Sort arrays A, B, and C (cost: n log n). Think of the arrays as queues
   (that is, "remove" elements from the left by increasing a start index).
2. Create current-intervals set (initially empty. Has O(log n) operations.)
2. While A not empty or B not empty or C not empty:
3.   get the lowest element from the first (if any) elements in A, B, and C.
4.   if it's an A:
5.     Add the corresponding interval to the current-intervals list
6.   else if it's a B:
7.      Remove the corresponding interval from the current-intervals list
8.   else it must be a C, so:
9.      The answer to the query corresponding to C is the current-intervals list
        (in the current state)

Answer 4

This is a more efficient version using ArrayLists:

        int len = arrA.length;
        ArrayList<Integer> A = new ArrayList<Integer>(len);
        ArrayList<Integer> B = new ArrayList<Integer>(len);
        for (int i=0; i<len; i++) {
            A.add(arrA[i]);
            B.add(arrB[i]);
        }

        for (int i = 0; i < C.length; i++) {
            int c = C[i];
            int j = 0;
            while (j<A.size() && A.get(j) <= c) {
                if (B.get(j) >= c) {
                    A.remove(j);
                    if (A.isEmpty()) return i+1;
                    B.remove(j);
                }
                else {
                    j++;
                }
            }
        }
        return 0;

Answer 5

Ok so based on your answer, we have no choice but to check each element of C against A and B. But since A and B are in ascending order, performance should be reasonable:

    int len = A.length;
    boolean[] eliminated = new boolean[len]; // initially all elements are false
    int totalEliminated = 0;

    for (int i = 0; i < C.length; i++) {
        int c = C[i];
        for (int j = 0; j < len && A[j] <= c; j++) {
            if (B[j] >= c && !eliminated[j]) {
                System.out.println(c + " eliminates " + A[j] + " - " + B[j]);
                eliminated[j] = true;
                if (++totalEliminated == len) {
                    return i+1;
                }
            }
        }
    }
    return 0;

Answer 6

If the input ranges are already ordered from smallest to largest (B[i] <= A[i+1]):

int bottomRangeIndex = 0;
int topRangeIndex = numberOfABRangesYouHave - 1;
int answerCounter = 0;

C.sort(); // Sort C so that it goes from smallest to largest number.

for number in C: {
    if (number < A[bottomRangeIndex]) {
        continue;
    } else if (number > B[topRangeIndex]) {
        return answerCounter;
    } else {
        while ((number > B[bottomRangeIndex++]) && (bottomRangeIndex <= topRangeIndex)) {
            // Just keeps incrementing bottomRangeIndex.
        }
        if (bottomRangeIndex > topRangeIndex) {
            return answerCounter;
        } else {
            answerCounter++;
            bottomRangeIndex++;
        }
    }
}

This might have some bug that I am not thinking of, but basically what this does is:

1. Sorts C. I know you say you can't do this, but I fail to see why unless it's a homework problem.
2. Skips checking anything in the A,B ranges if the number from C falls completely outside of those ranges. If the current number is greater than the biggest number in the A,B ranges (B[topRangeIndex]), return the current answer counter because no further element from C (sorted) could be in the A,B ranges again.
3. Since C is sorted and the current number is greater than the bottom element in all A,B ranges, starts checking if the number in C falls inside the B end of each A range. The number being checked is always the smallest element in C, so if it fails to fall within the B end of an A range, that A,B range should never be checked again so the bottomRangeIndex is incremented.
4. If every range has been eliminated by the while loop, we are done checking (the current element in C is greater than the biggest number in any A,B range, we do not need to check anything else.
5. If the number in C being checked was NOT greater than a number at the end of an A,B range (located at bottomRangeIndex), that A,B range contained an element from C. We increment the answer counter, move the bottomRangeIndex up, and continue.

Try this and see if it works. If this is homework and you really can't sort C, then you can modify this to give you the right answer with a small amount of tweaking, but I won't say how...