352. Data Stream as Disjoint Intervals
Approach
SortedDictionary of intervals keyed by start. On each Add,
merge with adjacent intervals on the left and right if they touch or overlap.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Design problems ask you to implement a data structure or system with specific API contracts. Common designs: LRU Cache (HashMap + doubly linked list), LFU Cache, Min Stack, Iterator, and streaming median. Focus on the time complexity required for each operation.
// Approach: SortedDictionary of intervals keyed by start. On each Add,
// merge with adjacent intervals on the left and right if they touch or overlap.
// Time: O(log n) per add Space: O(n)
public class SummaryRanges
{
private SortedDictionary<int, int[]> intervals = new SortedDictionary<int, int[]>();
public SummaryRanges()
{
}
public void AddNum(int val)
{
if (intervals.ContainsKey(val))
return;
// the maximum key in `intervals` < `key`
intervals.TryGetValue(val - 1, out int[] lo);
// the minimum key in `intervals` > `key`
intervals.TryGetValue(val + 1, out int[] hi);
// {lo, intervals[lo][1]} + val + {hi, intervals[hi][1]} = {lo, intervals[hi][1]}
if (lo != null && hi != null && lo[1] + 1 == val && val + 1 == hi[0])
{
lo[1] = hi[1];
intervals.Remove(hi[0]);
}
else if (lo != null && lo[1] + 1 >= val)
lo[1] = Math.Max(lo[1], val);
else if (hi != null && val + 1 == hi[0])
{
intervals[val] = new int[] { val, hi[1] };
intervals.Remove(hi[0]);
}
else
intervals[val] = new int[] { val, val };
}
public int[][] GetIntervals()
{
return intervals.Values.ToArray();
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.AddNum(value);
* int[][] param_2 = obj.GetIntervals();
*/