Data Stream as Disjoint Intervals

Problem#

Implement SummaryRanges supporting addNum(int) and getIntervals(). Maintain the list of disjoint intervals covering all values added so far.

Examples#

addNum(1); addNum(3); getIntervals() → [[1,1],[3,3]]
After addNum(2): getIntervals() → [[1,3]]

Constraints#

Up to 3 * 10^4 ops.

Hints#

Hint 1

Keep a std::map<int,int> keyed by start, value = end. Each add looks up neighboring intervals and possibly merges.

Approach#

std::map<int,int> ordered by interval start. On addNum(x): find the interval whose start ≤ x (upper_bound then step back). Decide whether x extends it, lies inside it (no-op), or is disjoint. Then check whether the right neighbor’s start equals x + 1 and merge.

Solution#

class SummaryRanges {
    map<int,int> mp; // start -> end
public:
    void addNum(int x) {
        auto next = mp.upper_bound(x);
        auto prev = next == mp.begin() ? mp.end() : prev_iter(next);
        // Case: x already covered by previous interval.
        if (prev != mp.end() && prev->second >= x) return;
        bool mergePrev = (prev != mp.end() && prev->second + 1 == x);
        bool mergeNext = (next != mp.end() && next->first == x + 1);
        if (mergePrev && mergeNext) {
            prev->second = next->second;
            mp.erase(next);
        } else if (mergePrev) {
            prev->second = x;
        } else if (mergeNext) {
            int ne = next->second;
            mp.erase(next);
            mp[x] = ne;
        } else {
            mp[x] = x;
        }
    }
    vector<vector<int>> getIntervals() {
        vector<vector<int>> out;
        out.reserve(mp.size());
        for (auto& [s, e] : mp) out.push_back({s, e});
        return out;
    }
private:
    static map<int,int>::iterator prev_iter(map<int,int>::iterator it) { return --it; }
};

import "sort"

type SummaryRanges struct {
    intervals [][2]int // sorted by start; each is [start, end]
}

func Constructor() SummaryRanges {
    return SummaryRanges{}
}

func (sr *SummaryRanges) AddNum(x int) {
    // Binary search for first interval with start > x.
    n := len(sr.intervals)
    nextIdx := sort.Search(n, func(i int) bool { return sr.intervals[i][0] > x })
    prevIdx := nextIdx - 1
    if prevIdx >= 0 && sr.intervals[prevIdx][1] >= x {
        return
    }
    mergePrev := prevIdx >= 0 && sr.intervals[prevIdx][1]+1 == x
    mergeNext := nextIdx < n && sr.intervals[nextIdx][0] == x+1
    switch {
    case mergePrev && mergeNext:
        sr.intervals[prevIdx][1] = sr.intervals[nextIdx][1]
        sr.intervals = append(sr.intervals[:nextIdx], sr.intervals[nextIdx+1:]...)
    case mergePrev:
        sr.intervals[prevIdx][1] = x
    case mergeNext:
        sr.intervals[nextIdx][0] = x
    default:
        sr.intervals = append(sr.intervals, [2]int{})
        copy(sr.intervals[nextIdx+1:], sr.intervals[nextIdx:])
        sr.intervals[nextIdx] = [2]int{x, x}
    }
}

func (sr *SummaryRanges) GetIntervals() [][]int {
    out := make([][]int, 0, len(sr.intervals))
    for _, iv := range sr.intervals {
        out = append(out, []int{iv[0], iv[1]})
    }
    return out
}

from typing import List
import bisect

class SummaryRanges:
    def __init__(self):
        self.intervals: List[List[int]] = []  # sorted by start; each is [start, end]

    def addNum(self, value: int) -> None:
        n = len(self.intervals)
        # First interval with start > value
        next_idx = bisect.bisect_right([iv[0] for iv in self.intervals], value) if False else \
                   bisect.bisect_right(self.intervals, [value, float('inf')])
        prev_idx = next_idx - 1
        if prev_idx >= 0 and self.intervals[prev_idx][1] >= value:
            return
        merge_prev = prev_idx >= 0 and self.intervals[prev_idx][1] + 1 == value
        merge_next = next_idx < n and self.intervals[next_idx][0] == value + 1
        if merge_prev and merge_next:
            self.intervals[prev_idx][1] = self.intervals[next_idx][1]
            self.intervals.pop(next_idx)
        elif merge_prev:
            self.intervals[prev_idx][1] = value
        elif merge_next:
            self.intervals[next_idx][0] = value
        else:
            self.intervals.insert(next_idx, [value, value])

    def getIntervals(self) -> List[List[int]]:
        return [list(iv) for iv in self.intervals]

class SummaryRanges {
    constructor() {
        this.intervals = []; // sorted by start; each is [start, end]
    }

    addNum(value) {
        const n = this.intervals.length;
        // First interval with start > value (binary search)
        let lo = 0, hi = n;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.intervals[mid][0] > value) hi = mid;
            else lo = mid + 1;
        }
        const nextIdx = lo;
        const prevIdx = nextIdx - 1;
        if (prevIdx >= 0 && this.intervals[prevIdx][1] >= value) return;
        const mergePrev = prevIdx >= 0 && this.intervals[prevIdx][1] + 1 === value;
        const mergeNext = nextIdx < n && this.intervals[nextIdx][0] === value + 1;
        if (mergePrev && mergeNext) {
            this.intervals[prevIdx][1] = this.intervals[nextIdx][1];
            this.intervals.splice(nextIdx, 1);
        } else if (mergePrev) {
            this.intervals[prevIdx][1] = value;
        } else if (mergeNext) {
            this.intervals[nextIdx][0] = value;
        } else {
            this.intervals.splice(nextIdx, 0, [value, value]);
        }
    }

    getIntervals() {
        return this.intervals.map((iv) => [iv[0], iv[1]]);
    }
}

class SummaryRanges {
    private final TreeMap<Integer, Integer> mp = new TreeMap<>(); // start -> end

    public SummaryRanges() {
    }

    public void addNum(int value) {
        Map.Entry<Integer, Integer> nextEntry = mp.higherEntry(value);
        Map.Entry<Integer, Integer> prevEntry = mp.floorEntry(value);
        if (prevEntry != null && prevEntry.getValue() >= value) return;
        boolean mergePrev = prevEntry != null && prevEntry.getValue() + 1 == value;
        boolean mergeNext = nextEntry != null && nextEntry.getKey() == value + 1;
        if (mergePrev && mergeNext) {
            mp.put(prevEntry.getKey(), nextEntry.getValue());
            mp.remove(nextEntry.getKey());
        } else if (mergePrev) {
            mp.put(prevEntry.getKey(), value);
        } else if (mergeNext) {
            int ne = nextEntry.getValue();
            mp.remove(nextEntry.getKey());
            mp.put(value, ne);
        } else {
            mp.put(value, value);
        }
    }

    public int[][] getIntervals() {
        int[][] out = new int[mp.size()][2];
        int idx = 0;
        for (Map.Entry<Integer, Integer> e : mp.entrySet()) {
            out[idx][0] = e.getKey();
            out[idx][1] = e.getValue();
            idx++;
        }
        return out;
    }
}

class SummaryRanges {
    private intervals: number[][] = []; // sorted by start; each is [start, end]

    addNum(value: number): void {
        const n = this.intervals.length;
        let lo = 0, hi = n;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.intervals[mid][0] > value) hi = mid;
            else lo = mid + 1;
        }
        const nextIdx = lo;
        const prevIdx = nextIdx - 1;
        if (prevIdx >= 0 && this.intervals[prevIdx][1] >= value) return;
        const mergePrev = prevIdx >= 0 && this.intervals[prevIdx][1] + 1 === value;
        const mergeNext = nextIdx < n && this.intervals[nextIdx][0] === value + 1;
        if (mergePrev && mergeNext) {
            this.intervals[prevIdx][1] = this.intervals[nextIdx][1];
            this.intervals.splice(nextIdx, 1);
        } else if (mergePrev) {
            this.intervals[prevIdx][1] = value;
        } else if (mergeNext) {
            this.intervals[nextIdx][0] = value;
        } else {
            this.intervals.splice(nextIdx, 0, [value, value]);
        }
    }

    getIntervals(): number[][] {
        return this.intervals.map((iv) => [iv[0], iv[1]]);
    }
}

Editorial#

Four cases on each add: covered, merge-with-prev only, merge-with-next only, merge-both, fresh interval. The ordered map gives O(log n) for the neighbor lookup; the rest is O(1). getIntervals is O(n) one-shot.

Complexity#

Time: O(log n) per add; O(n) for getIntervals.
Space: O(n).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#