Skip to main content
Talentd

Count Integers in Intervals - Solution & Explanation

HardDesignSegment TreeOrdered Set19 min readAsked at: Uber, Google, LinkedIn +1
Practice this problem

Problem Statement

Given an empty set of intervals, implement a data structure that can:

  • Add an interval to the set of intervals.
  • Count the number of integers that are present in at least one interval.

Implement the CountIntervals class:

  • CountIntervals() Initializes the object with an empty set of intervals.
  • void add(int left, int right) Adds the interval [left, right] to the set of intervals.
  • int count() Returns the number of integers that are present in at least one interval.

Note that an interval [left, right] denotes all the integers x where left <= x <= right.

 

Example 1:

Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]

Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. 
countIntervals.add(2, 3);  // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8);  // add [5, 8] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval [2, 3].
                           // the integers 5 and 6 are present in the interval [5, 8].
                           // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
                           // the integers 9 and 10 are present in the interval [7, 10].

 

Constraints:

  • 1 <= left <= right <= 109
  • At most 105 calls in total will be made to add and count.
  • At least one call will be made to count.

Approach Overview

Problem Overview: Design a data structure that supports two operations: add(left, right) to insert an interval and count() to return how many distinct integers are covered by all inserted intervals. Intervals can overlap, so the main challenge is maintaining the total number of unique integers without double-counting overlaps.

Approach 1: Interval Merging using Sorted List (O(n) add, O(1) count)

Store all disjoint intervals in a sorted list ordered by start value. When you call add(left, right), iterate through the list and merge any intervals that overlap with the new one. During merging, subtract the lengths of removed intervals from the running total and add the merged interval length back. The count() operation simply returns the maintained total. Each insertion may scan and merge multiple intervals, giving O(n) time for add and O(1) time for count, with O(n) space for stored intervals. This approach works well in Python or C++ using lists and binary search.

Approach 2: Balanced Tree (Ordered Set) (O(log n) add, O(1) count)

Use a balanced BST or ordered map keyed by interval start. For each add(left, right), locate the first overlapping interval using a tree search, then repeatedly merge all overlapping neighbors while updating the total covered count. Because the tree keeps intervals sorted automatically, locating and removing overlaps takes O(log n) per structural operation. The total count is tracked incrementally, so count() remains O(1). Space complexity is O(n). Languages like Java (TreeMap) and JavaScript (ordered structures) implement this cleanly. This solution models a classic Ordered Set design problem.

Although the problem tags also reference Segment Tree, a full segment tree across the range up to 109 is usually unnecessary unless you implement coordinate compression. Maintaining merged intervals in a tree is simpler and achieves the required efficiency.

Recommended for interviews: The balanced tree solution is typically expected. It shows you understand interval merging, ordered structures, and incremental counting. Starting with the sorted-interval merging idea demonstrates strong reasoning, while implementing it with a tree highlights practical design skills for dynamic data structures.

Approach 1: Approach 1: Interval Merging using Sorted List

Maintain a sorted list of non-overlapping intervals. When a new interval is added, merge it with existing overlapping or adjacent intervals. This allows efficient counting since each interval contributes exactly its length to the total count.

The constructor initializes an empty list to store intervals. When adding a new interval, it is appended to the list, and the list is sorted to ensure order. Overlapping intervals in the sorted list are then merged. Counting simply involves summing the lengths of all intervals.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log n) for sorting intervals during add operations.
Space Complexity: O(n) for storing intervals.

Try this approach in the editor →

Approach 2: Approach 2: Using Balanced Tree (Ordered Set)

This approach uses a self-balancing binary search tree or an ordered set to store and manage intervals. Using such data structures makes merging dynamic intervals efficient.

In this Java solution, a TreeMap is used to map the start of each interval to its end. This enables efficient lookup and merging of intervals when a new interval overlaps with existing ones. The total count of distinct integers is maintained and adjusted with each addition.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(log n) for adding intervals and counting, where n is the number of intervals stored.
Space Complexity: O(n) for storing intervals.

Try this approach in the editor →

Approach 3: Segment Tree (Dynamic Opening)

According to the problem description, we need to maintain a set of intervals that supports adding intervals and querying operations. For adding intervals, we can use a segment tree to maintain the interval set.

The segment tree divides the entire interval into multiple non-contiguous sub-intervals, with the number of sub-intervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we need to use lazy propagation to ensure efficiency.

  • Each node of the segment tree represents an interval;
  • The segment tree has a unique root node representing the entire range, such as [1, N];
  • Each leaf node of the segment tree represents a unit interval of length 1, [x, x];
  • For each internal node [l, r], its left child is [l, mid] and its right child is [mid+1, r], where mid = \lfloor (l + r) / 2 \rfloor (i.e., floor division).

Since the data range in the problem is large, we can use a dynamically opened segment tree. A dynamically opened segment tree means that we only open nodes when needed, rather than opening all nodes at the beginning, which saves space.

In terms of time complexity, each operation has a time complexity of O(log n). The space complexity is O(m times log n), where m is the number of operations and n is the data range.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Interval Merging using Sorted List

Time Complexity: O(n log n) for sorting intervals during add operations.
Space Complexity: O(n) for storing intervals.

Approach 2: Using Balanced Tree (Ordered Set)

Time Complexity: O(log n) for adding intervals and counting, where n is the number of intervals stored.
Space Complexity: O(n) for storing intervals.

Segment Tree (Dynamic Opening)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Interval Merging with Sorted ListO(n) per add, O(1) countO(n)Simple implementation when number of intervals is moderate
Balanced Tree / Ordered SetO(log n) add, O(1) countO(n)Best general solution for frequent updates and large interval sets

Video Solution

Count Integers in Intervals | Leetcode 2276 | Easy TreeMap | Live coding session • Coding Decoded • 2,759 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Count Integers in Intervals easy or hard?
Count Integers in Intervals is classified as a Hard problem. The challenge comes from designing a data structure that supports dynamic interval insertion while avoiding double counting and keeping operations efficient.
Count Integers in Intervals Python/Java solution
Python solutions often use a sorted list with binary search or external libraries like SortedContainers to maintain ordered intervals. Java implementations commonly rely on TreeMap to efficiently find and merge overlapping intervals while updating the total count.
How to solve Count Integers in Intervals efficiently?
Maintain a set of non-overlapping intervals sorted by start position. When adding a new interval, locate overlapping intervals, merge them into a single range, and update the stored total length. Ordered structures like TreeMap or balanced BSTs keep these operations around O(log n) time.
What is the best approach for Count Integers in Intervals?
The most practical approach uses a balanced tree (ordered set or TreeMap) to store non-overlapping intervals. Each add operation merges overlapping intervals and updates a running total of covered integers. This keeps insertion around O(log n) and count queries O(1). It scales well when many intervals are added dynamically.
Is Count Integers in Intervals asked at Google/Amazon/Meta?
Interval data structure design problems similar to this appear in interviews at companies like Google, Amazon, and Meta. They test understanding of interval merging, ordered maps, and maintaining aggregate values under dynamic updates.
What data structure is used in Count Integers in Intervals?
The typical solution uses an ordered set or balanced binary search tree to store disjoint intervals. Alternatives include segment trees with coordinate compression, but ordered maps are simpler and more memory efficient for this problem.
What is the time complexity of Count Integers in Intervals?
Using a balanced tree structure, the add(left, right) operation typically runs in O(log n) time for searching and merging neighboring intervals, while count() is O(1) because the total covered length is maintained incrementally. Space complexity is O(n) for storing disjoint intervals.

Ready to solve this problem?

Practice Count Integers in Intervals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Data Stream as Disjoint Intervals

Next

Insert Interval