Data Stream as Disjoint Intervals Solution in Java

Quick Links

Problem Description

Welcome to the world of data streams, where numbers flow like a river, and intervals are the bridges that connect them! The problem at hand is like trying to organize a chaotic party where guests (numbers) keep arriving, and you need to group them into neat little intervals.

Imagine you’re hosting a party, and your friends keep showing up at random times. You want to group them based on when they arrive. If Bob arrives at 5 PM and Alice at 6 PM, you can say they’re in the same interval. But if Charlie shows up at 8 PM, he’s in a different group. Now, if Bob and Alice decide to leave, and then Charlie arrives at 7 PM, you need to merge those intervals. Sounds fun, right?

In this problem, you’ll be managing a stream of integers and merging them into disjoint intervals. Your task is to implement a class that can add numbers and return the current list of disjoint intervals.

Code Solution


class SummaryRanges {
  public void addNum(int val) {
    if (intervals.containsKey(val))
      return;

    final Integer lo = intervals.lowerKey(val);
    final Integer hi = intervals.higherKey(val);

    if (lo != null && hi != null && intervals.get(lo)[1] + 1 == val && val + 1 == hi) {
      intervals.get(lo)[1] = intervals.get(hi)[1];
      intervals.remove(hi);
    } else if (lo != null && intervals.get(lo)[1] + 1 >= val) {
      intervals.get(lo)[1] = Math.max(intervals.get(lo)[1], val);
    } else if (hi != null && val + 1 == hi) {
      intervals.put(val, new int[] {val, intervals.get(hi)[1]});
      intervals.remove(hi);
    } else {
      intervals.put(val, new int[] {val, val});
    }
  }

  public int[][] getIntervals() {
    return intervals.values().stream().toArray(int[][] ::new);
  }

  private TreeMap intervals = new TreeMap<>();
}

Approach Explanation

The code uses a TreeMap to store the intervals. When a new number is added, it checks the existing intervals to see if it can merge with them or create a new interval. The logic is as follows:

Check for Duplicates: If the number already exists in the intervals, simply return.
Find Neighbors: Use lowerKey and higherKey to find the closest intervals around the new number.
Merge Intervals: Depending on the relationships between the new number and the neighboring intervals, merge them or create a new interval.

Time and Space Complexity

Time Complexity: The addNum function runs in O(log n) time due to the operations on the TreeMap, where n is the number of intervals.

Space Complexity: The space complexity is O(n) for storing the intervals.

Real-World Example

Think of a concert where people are arriving at different times. If the concert starts at 6 PM and people arrive at 5:59 PM, 6:00 PM, and 6:01 PM, they all belong to the same interval. If someone arrives at 6:05 PM, they form a new interval. If someone arrives at 6:02 PM, they merge into the existing interval. This is exactly what our code does with the data stream!