Data Structure to convert a stream of integers into a list of range

I'd not keep the original numbers, but aggregate them to ranges on the fly. This has the potential to reduce the number of elements by quite some factor (depending on the ordering and distribution of the incoming values). The task itself seems to imply that you expect contiguous ranges of integers to appear quite frequently in the input.

Then a newly incoming number can fall into one of a few cases:

• It is already contained in some range: then simply ignore the number (this is only relevant if duplicate inputs can happen).
• It is adjacent to none of the ranges so far: create a new single-element range.
• It is adjacent to exactly one range: extend that range by 1, downward or upward.
• It is adjacent to two ranges (i.e. fills the gap): merge the two ranges.

For the data structure holding the ranges, you want a good performance for the following operations:

• Find the place (position) for a given number.
• Insert a new element (range) at a given place.
• Merge two (neighbor) elements. This can be broken down into:
  • Remove an element at a given place.
  • Modify an element at a given place.

Depending on the expected number und sparsity of ranges, a sorted list of ranges might do. Otherwise, some kind of search tree might turn out helpful.

Anyway, start with the most readable approach, measure performance for typical cases, and decide whether some optimization is necessary.

I suggest maintaining a hashmap that maps each integer seen so far to the interval it belongs to.

Make sure that two numbers that are part of the same interval will point to the same interval object, not to copies; so that if you update an interval to extend it, all numbers can see it.

All operations are O(1), except the operation "merge two intervals" that happens if the stream produces integer x when we have two intervals [a, x - 1] and [x + 1, b]. The merge operation is proportional to the length of the shortest of these two intervals.

As a result, for a stream of n integers, the algorithm's complexity is O(n) in the best-case (where at most a few big merges happen) and O(n log n) in the worst-case (when we keep merging lots of intervals).

In python:

def add_element(intervals, x):
        if x in intervals: # do not do anything
            pass
        elif x + 1 in intervals and x - 1 in intervals: # merge two intervals
            i = intervals[x - 1]
            j = intervals[x + 1]
            if i[1]-i[0] > j[1]-j[0]: # j is shorter: update i, and make everything in j point to i
                i[1] = j[1]
                for y in range(j[0] - 1, j[1]+1):
                    intervals[y] = i
            else: # i is shorter: update j, and make everything in i point to j
                j[0] = i[0]
                for y in range(i[0], i[1] + 2):
                    intervals[y] = j
        elif x + 1 in intervals: # extend one interval to the left
            i = intervals[x + 1]
            i[0] = x
            intervals[x] = i
        elif x - 1 in intervals: # extend one interval to the right
            i = intervals[x - 1]
            i[1] = x
            intervals[x] = i
        else: # add a singleton
            intervals[x] = [x,x]
        return intervals

from random import shuffle
def main():
    stream = list(range(10)) * 2
    shuffle(stream)
    print(stream)
    intervals = {}
    for x in stream:
        intervals = add_element(intervals, x)
        print(x)
        print(set(map(tuple, intervals.values()))) # this line terribly inefficient because I'm lazy

if __name__=='__main__':
    main()

Output:

[1, 5, 8, 3, 9, 6, 7, 9, 3, 0, 6, 5, 8, 1, 4, 7, 2, 2, 0, 4]
1
{(1, 1)}
5
{(1, 1), (5, 5)}
8
{(8, 8), (1, 1), (5, 5)}
3
{(8, 8), (1, 1), (5, 5), (3, 3)}
9
{(8, 9), (1, 1), (5, 5), (3, 3)}
6
{(3, 3), (1, 1), (8, 9), (5, 6)}
7
{(5, 9), (1, 1), (3, 3)}
9
{(5, 9), (1, 1), (3, 3)}
3
{(5, 9), (1, 1), (3, 3)}
0
{(0, 1), (5, 9), (3, 3)}
6
{(0, 1), (5, 9), (3, 3)}
5
{(0, 1), (5, 9), (3, 3)}
8
{(0, 1), (5, 9), (3, 3)}
1
{(0, 1), (5, 9), (3, 3)}
4
{(0, 1), (3, 9)}
7
{(0, 1), (3, 9)}
2
{(0, 9)}
2
{(0, 9)}
0
{(0, 9)}
4
{(0, 9)}

You could use a Disjoint Set Forest implementation for this. If well-implemented, it gives a near linear time complexity for inserting elements into it. The amortized running time of each insert operation is Θ(α()) where α() is the inverse Ackermann function. For all practical purposes we can not distinguish this from O(1).

The extraction of the ranges can have a time complexity of O(), where is the number of ranges, provided that the disjoint set maintains the set of root nodes. If the ranges need to be sorted, then this extraction will have a time complexity of O(log), as it will then just perform the sort-operation on it.

Here is an implementation in Python:

class Node:
    def __init__(self, value):
        self.low = value
        self.parent = self
        self.size = 1
    
    def find(self):  # Union-Find: Path splitting
        node = self
        while node.parent is not node:
            node, node.parent = node.parent, node.parent.parent
        return node

class Ranges:
    def __init__(self):
        self.nums = dict()
        self.roots = set()
        
    def union(self, a, b): # Union-Find: Size-based merge
        a = a.find()
        b = b.find()
        if a is not b:
            if a.size > b.size:
                a, b = b, a
            self.roots.remove(a)  # Keep track of roots
            a.parent = b
            b.low = min(a.low, b.low)
            b.size = a.size + b.size
    
    def add(self, n):
        if n not in self.nums:
            self.nums[n] = node = Node(n)
            self.roots.add(node)
            if (n+1) in self.nums:
                self.union(node, self.nums[n+1])
            if (n-1) in self.nums:
                self.union(node, self.nums[n-1])

    def get(self):
        return sorted((node.low, node.low + node.size - 1) for node in self.roots)

# example run
ranges = Ranges()
for n in 4, 7, 1, 6, 2, 9, 5:
    ranges.add(n)

print(ranges.get())  # [(1, 2), (4, 7), (9, 9)]