Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Given an empty set of intervals, implement a data structure that can:
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 <= 109105 calls in total will be made to add and count.count.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Design · Segment Tree
["CountIntervals","add","add","count","add","count"] [[],[2,3],[7,10],[],[5,8],[]]
merge-intervals)insert-interval)data-stream-as-disjoint-intervals)my-calendar-iii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2276: Count Integers in Intervals
class Node {
Node left;
Node right;
int l;
int r;
int mid;
int v;
int add;
public Node(int l, int r) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private Node root = new Node(1, (int) 1e9 + 1);
public SegmentTree() {
}
public void modify(int l, int r, int v) {
modify(l, r, v, root);
}
public void modify(int l, int r, int v, Node node) {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v = node.r - node.l + 1;
node.add = v;
return;
}
pushdown(node);
if (l <= node.mid) {
modify(l, r, v, node.left);
}
if (r > node.mid) {
modify(l, r, v, node.right);
}
pushup(node);
}
public int query(int l, int r) {
return query(l, r, root);
}
public int query(int l, int r, Node node) {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
pushdown(node);
int v = 0;
if (l <= node.mid) {
v += query(l, r, node.left);
}
if (r > node.mid) {
v += query(l, r, node.right);
}
return v;
}
public void pushup(Node node) {
node.v = node.left.v + node.right.v;
}
public void pushdown(Node node) {
if (node.left == null) {
node.left = new Node(node.l, node.mid);
}
if (node.right == null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add != 0) {
Node left = node.left, right = node.right;
left.add = node.add;
right.add = node.add;
left.v = left.r - left.l + 1;
right.v = right.r - right.l + 1;
node.add = 0;
}
}
}
class CountIntervals {
private SegmentTree tree = new SegmentTree();
public CountIntervals() {
}
public void add(int left, int right) {
tree.modify(left, right, 1);
}
public int count() {
return tree.query(1, (int) 1e9);
}
}
/**
* Your CountIntervals object will be instantiated and called as such:
* CountIntervals obj = new CountIntervals();
* obj.add(left,right);
* int param_2 = obj.count();
*/
// Accepted solution for LeetCode #2276: Count Integers in Intervals
type Node struct {
left *Node
right *Node
l int
r int
mid int
v int
add int
}
type SegmentTree struct {
root *Node
}
func newNode(l, r int) *Node {
return &Node{
left: nil,
right: nil,
l: l,
r: r,
mid: (l + r) / 2,
v: 0,
add: 0,
}
}
func newSegmentTree() *SegmentTree {
return &SegmentTree{
root: newNode(1, 1000000001),
}
}
func (st *SegmentTree) modify(l, r, v int, node *Node) {
if node == nil {
node = st.root
}
if l > r {
return
}
if node.l >= l && node.r <= r {
node.v = node.r - node.l + 1
node.add = v
return
}
st.pushdown(node)
if l <= node.mid {
st.modify(l, r, v, node.left)
}
if r > node.mid {
st.modify(l, r, v, node.right)
}
st.pushup(node)
}
func (st *SegmentTree) query(l, r int, node *Node) int {
if node == nil {
node = st.root
}
if l > r {
return 0
}
if node.l >= l && node.r <= r {
return node.v
}
st.pushdown(node)
v := 0
if l <= node.mid {
v += st.query(l, r, node.left)
}
if r > node.mid {
v += st.query(l, r, node.right)
}
return v
}
func (st *SegmentTree) pushup(node *Node) {
node.v = node.left.v + node.right.v
}
func (st *SegmentTree) pushdown(node *Node) {
if node.left == nil {
node.left = newNode(node.l, node.mid)
}
if node.right == nil {
node.right = newNode(node.mid+1, node.r)
}
if node.add != 0 {
left := node.left
right := node.right
left.add = node.add
right.add = node.add
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
node.add = 0
}
}
type CountIntervals struct {
tree *SegmentTree
}
func Constructor() CountIntervals {
return CountIntervals{
tree: newSegmentTree(),
}
}
func (ci *CountIntervals) Add(left, right int) {
ci.tree.modify(left, right, 1, nil)
}
func (ci *CountIntervals) Count() int {
return ci.tree.query(1, 1000000000, nil)
}
/**
* Your CountIntervals object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(left,right);
* param_2 := obj.Count();
*/
# Accepted solution for LeetCode #2276: Count Integers in Intervals
class Node:
__slots__ = ("left", "right", "l", "r", "mid", "v", "add")
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) // 2
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e9) + 1)
def modify(self, l, r, v, node=None):
if node is None:
node = self.root
if l > r:
return
if node.l >= l and node.r <= r:
node.v = node.r - node.l + 1
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if node is None:
node = self.root
if l > r:
return 0
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v += self.query(l, r, node.left)
if r > node.mid:
v += self.query(l, r, node.right)
return v
def pushup(self, node):
node.v = node.left.v + node.right.v
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add != 0:
left, right = node.left, node.right
left.add = node.add
right.add = node.add
left.v = left.r - left.l + 1
right.v = right.r - right.l + 1
node.add = 0
class CountIntervals:
def __init__(self):
self.tree = SegmentTree()
def add(self, left, right):
self.tree.modify(left, right, 1)
def count(self):
return self.tree.query(1, int(1e9))
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left, right)
# param_2 = obj.count()
// Accepted solution for LeetCode #2276: Count Integers in Intervals
/**
* [2276] Count Integers in Intervals
*
* 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 <= 10^9
* At most 10^5 calls in total will be made to add and count.
* At least one call will be made to count.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/count-integers-in-intervals/
// discuss: https://leetcode.com/problems/count-integers-in-intervals/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
// Credit: https://leetcode.com/problems/count-integers-in-intervals/solutions/2375879/rust-solution-using-btreemap-by-xiaoping-pshe/
struct CountIntervals {
count: i32,
map: std::collections::BTreeMap<i32, i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl CountIntervals {
fn new() -> Self {
let mp: std::collections::BTreeMap<i32, i32> = std::collections::BTreeMap::new();
Self { count: 0, map: mp }
}
fn add(&mut self, left: i32, right: i32) {
let (mut left, mut right) = (left, right);
self.count += right - left + 1;
if self.map.is_empty() {
self.map.insert(left, right);
return;
}
let (a, _) = self.map.iter().next().unwrap();
let (_, b) = self.map.iter().rev().next().unwrap();
if a - 1 > right || b + 1 < left {
self.map.insert(left, right);
return;
}
if let Some((&key, &value)) = self.map.range(..left + 1).rev().next() {
if value + 1 >= left {
if value > right {
self.count -= right - left + 1;
} else {
self.count -= value + 1 - left;
}
left = key;
right = right.max(value);
}
}
let mut done = false;
while done == false {
done = true;
if let Some((&key, &value)) = self.map.range(left + 1..).next() {
if value > right {
break;
}
self.count -= value - key + 1;
self.map.remove(&key);
done = false;
}
}
if let Some((&key, &value)) = self.map.range(left + 1..).next() {
if right + 1 >= key {
self.count -= right + 1 - key;
right = value;
self.map.remove(&key);
}
}
self.map.insert(left, right);
}
fn count(&self) -> i32 {
self.count
}
}
/**
* Your CountIntervals object will be instantiated and called as such:
* let obj = CountIntervals::new();
* obj.add(left, right);
* let ret_2: i32 = obj.count();
*/
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_2276_example_1() {
let mut count_intervals = CountIntervals::new(); // initialize the object with an empty set of intervals.
count_intervals.add(2, 3); // add [2, 3] to the set of intervals.
count_intervals.add(7, 10); // add [7, 10] to the set of intervals.
assert_eq!(count_intervals.count(), 6); // 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].
count_intervals.add(5, 8); // add [5, 8] to the set of intervals.
assert_eq!(count_intervals.count(), 8); // 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].
}
}
// Accepted solution for LeetCode #2276: Count Integers in Intervals
class CountIntervals {
left: null | CountIntervals;
right: null | CountIntervals;
start: number;
end: number;
sum: number;
constructor(start: number = 0, end: number = 10 ** 9) {
this.left = null;
this.right = null;
this.start = start;
this.end = end;
this.sum = 0;
}
add(left: number, right: number): void {
if (this.sum == this.end - this.start + 1) return;
if (left <= this.start && right >= this.end) {
this.sum = this.end - this.start + 1;
return;
}
let mid = (this.start + this.end) >> 1;
if (!this.left) this.left = new CountIntervals(this.start, mid);
if (!this.right) this.right = new CountIntervals(mid + 1, this.end);
if (left <= mid) this.left.add(left, right);
if (right > mid) this.right.add(left, right);
this.sum = this.left.sum + this.right.sum;
}
count(): number {
return this.sum;
}
}
/**
* Your CountIntervals object will be instantiated and called as such:
* var obj = new CountIntervals()
* obj.add(left,right)
* var param_2 = obj.count()
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.