CODEWITHSUNDEEP
javaalgorithmdata-structures
unknown_boundaries
unknown_boundaries

Reputation: 1580

Create intervals from integers

I'm looking for efficient ways for creating the Interval,

Interval - (startIndex [inclusive], endIndex [exclusive])

from the unsorted integer array.

For example,

Array A - [3, 1, 8, 5, 11, 10, 2]

should result in ordered list of Interval

ordered-List - [(1, 4), (5, 6), (8, 9), (10, 12)]

My initial thought is to sort this and scan from left to right creating the intervals understanding where the next element is not continuous.

Can we do this in linear time using modified Interval Tree concept, or is there any better way to do this?

PS: I'm OK with O(N) space.

Thanks in advance.

EDIT: Since my range lies in [0:1000], and number of elements at a time should be no more than 1000, I went through sorted way, however I still see the opportunity of improving this. My code:

private class Interval {
    private final int startIndex; // inclusive
    private final int endIndex; // exclusive

    private Interval(int startIndex, int endIndex) {
        Validate.isTrue(startIndex >= 0, "start-index (0-based): " + startIndex + ",  is lesser than 0.");
        Validate.isTrue(startIndex < endIndex, "start index " + startIndex + ", is out of bound with respect to end index " + endIndex + ".");
        Validate.isTrue(endIndex <= numberOfSlides(), "end index " + endIndex + ", points to slide that doesn't exist.");

        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    private int getRange() {
        return this.endIndex - this.startIndex;
    }

    private int startIndex() {
        return this.startIndex;
    }
}

private List<Interval> createIntervals(int[] slideIndexes) {
    Validate.notNull(slideIndexes, "The array of slide indexes is null!");
    Validate.isTrue(slideIndexes.length != 0, "The array of slide indexes is empty!");
    final List<Interval> intervals = new ArrayList<>();
    Arrays.sort(slideIndexes);        
    int curStart = slideIndexes[0], lastLink = curStart + 1;
    for (int i = 1; i < slideIndexes.length; i++) {
        if (slideIndexes[i] == lastLink - 1) { // handles duplicates!
            continue;
        } else if (slideIndexes[i] != lastLink) {
            intervals.add(new Interval(curStart, lastLink));
            curStart = slideIndexes[i];
        }
        lastLink = slideIndexes[i] + 1;
    }
    intervals.add(new Interval(curStart, lastLink));

    return intervals;
}

Upvotes: 4

Views: 2865

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 133995

You probably can't do better than O(n log n) in the general case unless you use extra space proportional to the highest value item, as shown in Pham Trung's algorithm, which is basically a counting sort.

Creating a set of contiguous intervals for an unsorted list of items is at its heart a sorting algorithm. For example, imagine that your list of items is [7,0,3,9,8,4,5,2,1,6]. That is the single closed interval (0,10). If you could compute that in less than O(n log n) time without using extra memory, then you could sort an arbitrary array in less than O(n log n) time. But we already know that comparison sorting has a lower bound of O(n log n).

Granted, if you know that your array contains a single closed interval, then if you know the min and max, you can sort it in linear time. But if you don't know how many intervals the items in the array represent, then you either end up using a non-comparison sort (counting sort, radix sort, etc.) with additional space at least proportional to N, or you do a comparison sort.

Upvotes: 1

Sildoreth
Sildoreth

Reputation: 1915

The way I would do it is:

  1. Use a fast sorting algorithm to sort the list first

  2. Loop through the sorted list – as you said – and account for the non-contiguous cases

Yes, this will give you a runtime of O(n log n). But unless you're expecting the array to be super-huge – like 1 million elements or more – this should not be a problem. Ultimately, this approach should be adequately fast.

For what it's worth, there aren't even 1 million seconds in a day: (24 hours) * (60 mins/hour) * (60 secs/min) = 86400 seconds. I don't know if that's applicable, but you are using a class named "Interval", which tends to hint at "time".

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

If the value of each element in array A is small, we can use a frequency table fre to mark the occurrence of each element in A.

int[]fre = //
for(int i : A)
   fre[i]++;

After this, you can apply your old algorithm on array fre to create those intervals.

for(int i = 50; i <= 1000; i++){
    if(fre[i] == 0){
       //Do something
    }else{
       //Do other thing
    }
}

Time complexity of this Algorithm is O(max(n,1000)), with n is the number of element in A.

Upvotes: 2

Related Questions