2276. Count Integers in Intervals

HardDesignSegment TreeOrdered Set
Leetcode Link

Problem Description

The LeetCode problem requires us to construct a data structure that supports adding intervals and counting the number of unique integer elements that lie within at least one of those intervals. After an interval is added, we need to keep track of all the unique numbers covered by all intervals. Specifically, the intervals are inclusive, meaning that if we add the interval [left, right], it includes all integers x where left <= x <= right.

Intuition

The intuition behind the solution is to use a segment tree data structure to efficiently manage the intervals and calculate the count of unique numbers. A segment tree is a tree data structure ideal for scenarios where we have to perform operations on interval or segments. It allows us to perform both updates and queries in logarithmic time.

For this particular problem, the segment tree nodes need to keep track of whether the entire segment is covered by any intervals (indicated by a tag) and the total count of unique numbers in that segment (tot). Each node represents a segment; if it is entirely covered by at least one interval (i.e., no part of the segment is outside any interval), we mark tag as 1, and tot becomes the size of that segment.

By utilizing lazy propagation in the segment tree, we avoid unnecessary updates to nodes. Lazy propagation means that unless necessary, we do not instantly update or query each child of a node. Instead, we mark the node as updated (tag = 1) and postpone updating its children until we specifically need to descend into them for further updates or queries. This technique significantly optimizes performance because not all nodes need to be looked at if a large chunk of them is entirely covered by the new interval.

When adding a new interval [left, right], we update the relevant segments of the tree. If an interval completely overlaps a segment, we set its tag to 1, and tot to the size of that segment. If the interval only partially covers the segment, we recursively update the corresponding child segments.

The count method simply returns the total count of unique numbers in all intervals, which is stored at the root of the segment tree.

This solution efficiently handles a series of interval additions and keeps an up-to-date count of the number of unique elements in all intervals, which can be returned in constant time.

Learn more about Segment Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

To implement the solution, we use a Segment Tree data structure, which is a binary tree structure that efficiently supports both update and query operations on intervals. Here's how we use it to approach the problem:

  1. Node Structure - We define a class Node that represents a segment in the segment tree. Each node has four properties:

    • tag: A lazy propagation flag to indicate if the whole segment that the node represents is fully covered by intervals.
    • tot: The total count of unique numbers within the intervals covered by this segment.
    • left: Reference to the left child node in the segment tree.
    • right: Reference to the right child node in the segment tree.

  2. Initiation - The CountIntervals class constructor initializes the segment tree by creating a root node. The root node's range is selected to cover the entire range of possible values (0 to 1000000010 in this implementation).

  3. Adding Intervals (add method) - When a new interval [left, right] is added, we need to update our segment tree; this is done by calling the update method of the root node.

Here’s the update algorithm in detail:

  • The update operation is applied recursively. If the current segment represented by the node is fully covered by the interval being added, we mark the tag as 1 and set tot to the size of the segment (b - a + 1).
  • The recursion stops when the interval fully covers the segment corresponding to the current node, or the node is already fully marked (self.tag == 1).
  • If the interval only partially covers the segment, we split the interval into two subintervals at the midpoint and recursively update the left and right child nodes, if they exist. If a child does not exist, we create it at this point. After updating children, we update the current node's tot to be the sum of the children's tots.
  • The use of lazy propagation means we don't immediately update all descendants of a node; instead, we propagate updates as necessary to maintain correct counts when querying.
  1. Counting (count method) - This method is straightforward; it simply returns the total count of unique numbers represented by the root of the segment tree (self.tree.tot). Since the tree is kept up-to-date by the add method, this value is readily available.

This approach allows for efficient operations on intervals and maintains an accurate count of the numbers contained in at least one interval with the Segment Tree's inherent logarithmic time complexity for updates and queries.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

To illustrate the solution approach described, let's consider a scenario where we're initially working with an empty set of intervals and we want to add intervals [1,3] and [2,5] to our data structure. We then want to count the number of unique integer elements covered by these intervals.

  1. Initiation: Initialize the segment tree. The root node will cover the full range of possible values.

  2. Adding interval [1,3]:

    • Call the update method to add interval [1,3].
    • Initially, no nodes are fully covered, so we will end up creating nodes to represent the required ranges and mark them accordingly.
    • After the update, we would have a tree where the segments [1,3] are marked with tag = 1 and tot = 3 since there are three unique numbers (1, 2, 3).

  3. Adding interval [2,5]:

    • Call the update method to add interval [2,5].
    • We check if the current node's segment is covered by [2,5].
    • Nodes representing segments [2,3] are already marked, so we don't update them.
    • Segments [4,5] need to be updated. If nodes for these segments don't exist, we create them and mark them as covered (setting tag = 1 and tot to their respective segment sizes).

  4. Counting unique elements:

    • We call the count method to find the total count of unique numbers in all intervals.
    • This is a straightforward tree query; the segment tree's root holds the total count in its tot variable.
    • In this case, it should return tot = 5 as there are five unique numbers (1 through 5) covered by the added intervals [1,3] and [2,5].

Throughout our operations, we use lazy propagation to update nodes only as necessary. This ensures our updates are efficient, and when we call count, the segment tree has already accounted for all the unique elements in the added intervals.

Solution Implementation

1class Node:
2    def __init__(self):
3        self.is_full = 0  # use a flag to indicate if the node covers a full interval
4        self.total = 0  # store the total count of intervals in this node
5        self.left_child = None  # left subtree
6        self.right_child = None  # right subtree
7
8    def update(self, left, right, lower_bound, upper_bound):
9        # Do not update if the node is already marked as fully covered
10        if self.is_full == 1:
11            return
12      
13        mid = (lower_bound + upper_bound) >> 1  # calculate the midpoint for the current interval
14      
15        # If the current interval completely corresponds with the node interval, set as full
16        if left == lower_bound and right == upper_bound:
17            self.is_full = 1
18            self.total = upper_bound - lower_bound + 1
19            return
20      
21        # Lazily create left and right child nodes if they don't exist
22        if not self.left_child:
23            self.left_child = Node()
24        if not self.right_child:
25            self.right_child = Node()
26      
27        # If the update interval overlaps with the left side, recursively update the left child
28        if mid >= left:
29            self.left_child.update(left, min(mid, right), lower_bound, mid)
30      
31        # If the update interval overlaps with the right side, recursively update the right child
32        if mid + 1 <= right:
33            self.right_child.update(max(mid + 1, left), right, mid + 1, upper_bound)
34      
35        # After updating children, reset the node's full status and calculate the new total
36        self.is_full = 0
37        self.total = 0
38        if self.left_child:
39            self.total += self.left_child.total
40        if self.right_child:
41            self.total += self.right_child.total
42
43
44class CountIntervals:
45    def __init__(self):
46        self.root = Node()  # initialize the root node of the segment tree
47
48    def add(self, left: int, right: int) -> None:
49        # Add a new interval [left, right] to the segment tree
50        self.root.update(left, right, 0, 1000000010)
51
52    def count(self) -> int:
53        # Retrieve the total count of intervals from the segment tree
54        return self.root.total
55
56
57# Example usage:
58# obj = CountIntervals()
59# obj.add(left, right)
60# total_intervals = obj.count()
61
1class Node {
2    Node left;
3    Node right;
4    int start;
5    int end;
6    int mid;
7    int value;
8    int add;
9
10    // Constructor for Node which sets up the segment range and calculates the mid point
11    public Node(int start, int end) {
12        this.start = start;
13        this.end = end;
14        this.mid = (start + end) >> 1; // Equivalent to (start + end) / 2
15    }
16}
17
18// A class representing a segment tree data structure
19class SegmentTree {
20    private Node root = new Node(1, (int) 1e9 + 1); // Constructs the root node covering the entire range
21
22    // Constructor is empty since the root is already initialized
23    public SegmentTree() {
24    }
25
26    // Public method to modify a range of values in the segment tree
27    public void modify(int left, int right, int value) {
28        modify(left, right, value, root);
29    }
30
31    // Helper method to recursively modify the range [left, right] with the given value
32    private void modify(int left, int right, int value, Node node) {
33        if (left > right) {
34            return;
35        }
36        if (node.start >= left && node.end <= right) {
37            node.value = node.end - node.start + 1;
38            node.add = value;
39            return;
40        }
41        pushDown(node);
42        if (left <= node.mid) {
43            modify(left, right, value, node.left);
44        }
45        if (right > node.mid) {
46            modify(left, right, value, node.right);
47        }
48        pushUp(node);
49    }
50
51    // Public method to query the value of a range in the segment tree
52    public int query(int left, int right) {
53        return query(left, right, root);
54    }
55
56    // Helper method to recursively query the range [left, right]
57    private int query(int left, int right, Node node) {
58        if (left > right) {
59            return 0;
60        }
61        if (node.start >= left && node.end <= right) {
62            return node.value;
63        }
64        pushDown(node);
65        int totalValue = 0;
66        if (left <= node.mid) {
67            totalValue += query(left, right, node.left);
68        }
69        if (right > node.mid) {
70            totalValue += query(left, right, node.right);
71        }
72        return totalValue;
73    }
74
75    // Method to update the node's value based on values of its children
76    private void pushUp(Node node) {
77        node.value = node.left.value + node.right.value;
78    }
79
80    // Method to propagate the lazy update values down to a node's children
81    private void pushDown(Node node) {
82        if (node.left == null) {
83            node.left = new Node(node.start, node.mid);
84        }
85        if (node.right == null) {
86            node.right = new Node(node.mid + 1, node.end);
87        }
88        if (node.add != 0) {
89            Node left = node.left, right = node.right;
90            left.add = node.add;
91            right.add = node.add;
92            left.value = left.end - left.start + 1;
93            right.value = right.end - right.start + 1;
94            node.add = 0;
95        }
96    }
97}
98
99// Class to count intervals using SegmentTree
100class CountIntervals {
101    private SegmentTree tree = new SegmentTree();
102
103    // Constructor is empty since the SegmentTree is already initialized
104    public CountIntervals() {
105    }
106
107    // Method to add an interval in the SegmentTree
108    public void add(int left, int right) {
109        tree.modify(left, right, 1);
110    }
111
112    // Method to count the covered intervals in the SegmentTree
113    public int count() {
114        return tree.query(1, (int) 1e9);
115    }
116}
117
118/**
119 * Usage:
120 *
121 *  CountIntervals obj = new CountIntervals();
122 *  obj.add(left, right);
123 *  int count = obj.count();
124 */
125
1#include <iostream>
2#include <memory>
3using namespace std;
4
5class CountIntervals {
6private:
7    // The left child in the segment tree.
8    unique_ptr<CountIntervals> left;
9
10    // The right child in the segment tree.
11    unique_ptr<CountIntervals> right;
12
13    // The start of the interval.
14    int start;
15
16    // The end of the interval.
17    int end;
18
19    // The sum of intervals covered.
20    int sum;
21
22public:
23    /**
24     * Initializes a new instance of the CountIntervals class.
25     * @param start The start index of the intervals.
26     * @param end The end index of the intervals.
27     */
28    CountIntervals(int start = 0, int end = 1000000000) : start(start), end(end), sum(0) {}
29
30    /**
31     * Adds a new interval to the segment tree.
32     * @param left The start index of the interval to add.
33     * @param right The end index of the interval to add.
34     */
35    void add(int left, int right) {
36        // Do nothing if the current node is fully covered.
37        if (sum == (end - start + 1)) return;
38
39        // If the current interval is completely within the new interval,
40        // update the sum of this node to the total number of elements in this interval.
41        if (left <= this->start && right >= this->end) {
42            sum = this->end - this->start + 1;
43            return;
44        }
45
46        // Calculate the mid-point to divide the interval into two halves.
47        int mid = (this->start + this->end) / 2;
48
49        // Lazily initialize child nodes if they are not created yet.
50        if (!this->left) this->left = make_unique<CountIntervals>(this->start, mid);
51        if (!this->right) this->right = make_unique<CountIntervals>(mid + 1, this->end);
52
53        // Recursively add the interval to the left or right child.
54        if (left <= mid) this->left->add(left, right);
55        if (right > mid) this->right->add(left, right);
56
57        // Update the sum to the total of both children's sums.
58        this->sum = (this->left ? this->left->sum : 0) + (this->right ? this->right->sum : 0);
59    }
60
61    /**
62     * Gets the total number of unique integers added to the intervals.
63     * @returns The total count of unique integers.
64     */
65    int count() {
66        return sum;
67    }
68};
69
70/**
71 * Example of how to use the CountIntervals class.
72 */
73int main() {
74    // Create an instance of CountIntervals
75    CountIntervals intervals;
76    // Adds the interval [1, 3]
77    intervals.add(1, 3);
78    // Adds the interval [5, 7]
79    intervals.add(5, 7);
80    // Outputs the count of unique integers in the intervals, which should be 6 in this case.
81    cout << intervals.count() << endl;
82
83    return 0;
84}
85
1class CountIntervals {
2    // The left child in the segment tree.
3    private left: CountIntervals | null;
4
5    // The right child in the segment tree.
6    private right: CountIntervals | null;
7
8    // The start of the interval.
9    private start: number;
10
11    // The end of the interval.
12    private end: number;
13
14    // The sum of intervals covered.
15    private sum: number;
16
17    /**
18     * Initializes a new instance of the CountIntervals class.
19     * @param start The start index of the intervals.
20     * @param end The end index of the intervals.
21     */
22    constructor(start: number = 0, end: number = 10 ** 9) {
23        this.left = null;
24        this.right = null;
25        this.start = start;
26        this.end = end;
27        this.sum = 0;
28    }
29
30    /**
31     * Adds a new interval to the segment tree.
32     * @param left The start index of the interval to add.
33     * @param right The end index of the interval to add.
34     */
35    add(left: number, right: number): void {
36        // Do nothing if the current node is fully covered.
37        if (this.sum === this.end - this.start + 1) return;
38
39        // If the current interval is completely within the new interval,
40        // update the sum of this node to the total number of elements in this interval.
41        if (left <= this.start && right >= this.end) {
42            this.sum = this.end - this.start + 1;
43            return;
44        }
45
46        // Calculate the mid-point to divide the interval into two halves.
47        const mid = Math.floor((this.start + this.end) / 2);
48
49        // Lazily initialize child nodes if they are not created yet.
50        if (!this.left) this.left = new CountIntervals(this.start, mid);
51        if (!this.right) this.right = new CountIntervals(mid + 1, this.end);
52
53        // Recursively add the interval to the left or right child.
54        if (left <= mid) this.left.add(left, right);
55        if (right > mid) this.right.add(left, right);
56
57        // Update the sum to the total of both children's sums.
58        this.sum = (this.left ? this.left.sum : 0) + (this.right ? this.right.sum : 0);
59    }
60
61    /**
62     * Gets the total number of unique integers added to the intervals.
63     * @returns The total count of unique integers.
64     */
65    count(): number {
66        return this.sum;
67    }
68}
69
70/**
71 * Example of how to use the CountIntervals class.
72 */
73const intervals = new CountIntervals();
74intervals.add(1, 3); // Adds the interval [1, 3]
75intervals.add(5, 7); // Adds the interval [5, 7]
76console.log(intervals.count()); // Should output the count of unique integers in the intervals
77
Not Sure What to Study? Take the 2-min Quiz：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

The time complexity of the add method is O(log N) where N is the range of the intervals, because update function divides the interval into two halves each time, similar to a binary search. However, it also depends on the distribution of the intervals added which could worsen the time complexity if the intervals are distributed in such a way that they lead to the creation of many nodes in the segments.

For count, the time complexity is O(1) as it merely returns the total number of intervals (tot) stored at the root of the segment tree.

Space Complexity

The space complexity can be in the worst case O(N) where N is the range of the intervals. This would be the case if the update function is called in such a way that every possible interval becomes a node, effectively storing the whole segment tree in memory. However, the space complexity in typical use-cases would be better than this, since many intervals may overlap, reducing the number of nodes needed to represent the intervals.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫