CODEWITHSUNDEEP
javaintervalssortedlist
wfmn17
wfmn17

Reputation: 204

Create intervals in a sorted array

Let's say I have a sorted array of {1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 21, 23, 25, 26}. I'd like to put these elements into intervals the following way:

1..5
7..10
15..16
21..21
23..23
25..26

In reality I have much bigger data, so I would need an algorithm with a good runtime.

What I had in mind is the following: Separate the array into 2 parts, and with 4 loops go through the array. One loop from 0 index, 2 loop from middle of array and 1 loop from the end of it. Every loop would check if the current and the next element's diff is 1, if yes, then go to next element, else create an interval from previous elements and start a new interval from the next element.

My question is that is it a good approach, or is there a better way? Please pseudo or java code.

Upvotes: 3

Views: 4158

Answers (4)

milan
milan

Reputation: 12420

Another version, with two pointers (python):

def compress_to_range(vector):
    # O(n) in time, just one pass thru the list
    result = []
    i = 0
    while i < len(vector):
        j = i+1
        while j < len(vector) and vector[j] == vector[j-1]+1:
            j += 1
        # j now points to the element outside the interval
        result.append([vector[i], vector[j-1]])
        i = j

    return result

Upvotes: 0

DAle
DAle

Reputation: 9127

Linear solution:

int intervalStart = a[0];
for (int i = 1; i < a.length; ++i) {
    if (a[i] > a[i-1] + 1) {
        outputInterval(intervalStart, a[i-1]);
        intervalStart = a[i];
    }
}
outputInterval(intervalStart, a[a.length-1]);

Runnable version: https://ideone.com/NZ2Uex

Upvotes: 3

&#181;Theory
&#181;Theory

Reputation: 178

You're trying to get the lists of consecutive integers.

The simplest and most naive way in O(n) is to do something like this :

List<List<Integer>> list_of_sublists = new List<>(); // The list of sublists
int lastElement = elements[0];
List<Integer> subList = new List <>(); // The current sublist
subList.add(lastElement);
int i = 1; // We start with index 1 because index 0 is already done
while (i < elements.length){
   int element = elements[i]
   if !(lastElement + 1 == element)){ //If not a consecutive we start a new list
       list_of_sublists.add(subList);
       subList = new List<>();
   }
   lastElement = element;
   subList.add(element);
   i ++;

//We didn't add the last sublist
list_of_sublists.add(subList);
return list_of_sublists;

You can easily adapt to arrays by getting the intervals and copying afterwars each interval.

Upvotes: 1

nasukkin
nasukkin

Reputation: 2540

You could consider having an array of IntRanges from Apache Commons to represent such a concept.

Yes, it requires a 3rd-party library, but it's Apache Commons, after all.

Upvotes: 1

Related Questions