Introduction

In this blog post, we will explore how to solve the LeetCode problem "352" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals. Implement the SummaryRanges class: SummaryRanges() Initializes the object with an empty stream. void addNum(int value) Adds the integer value to the stream. int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi]. The answer should be sorted by starti. Example 1: Input ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] Output [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] Explanation SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // return [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // return [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // return [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // return [[1, 3], [6, 7]] Constraints: 0 <= value <= 104 At most 3 * 104 calls will be made to addNum and getIntervals. At most 102 calls will be made to getIntervals. Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Explanation

• Binary Search and Merge: Use binary search to find the correct position to insert the new number into the sorted list of intervals. Merge intervals if the new number falls within or is adjacent to existing intervals.
  • Interval Representation: Represent intervals as pairs of integers (start, end).
  • Sorted List: Maintain a sorted list of disjoint intervals to allow for efficient searching and merging.

• Runtime Complexity: O(log n) for addNum (due to binary search and merging), O(n) for getIntervals (to copy the list). Storage Complexity: O(n), where n is the number of intervals.

Code

    import bisect

class SummaryRanges:

    def __init__(self):
        self.intervals = []

    def addNum(self, value: int) -> None:
        # Find the insertion point using binary search
        i = bisect.bisect_left(self.intervals, [value, value])

        # Case 1: Value overlaps with existing interval(s) or is adjacent to existing interval(s)
        # Check if value can be merged with the interval before
        if i > 0 and self.intervals[i-1][1] >= value - 1:
            # Extend the previous interval if needed
            self.intervals[i-1][1] = max(self.intervals[i-1][1], value)

            # Merge with the next interval if adjacent or overlapping
            if i < len(self.intervals) and self.intervals[i][0] <= self.intervals[i-1][1] + 1:
                self.intervals[i-1][1] = max(self.intervals[i-1][1], self.intervals[i][1])
                del self.intervals[i]
        # Check if value can be merged with the interval after
        elif i < len(self.intervals) and self.intervals[i][0] == value + 1:
            self.intervals[i][0] = value
        # Case 2: Value is a new interval
        else:
            self.intervals.insert(i, [value, value])

    def getIntervals(self) -> list[list[int]]:
        return self.intervals

# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()