DSA-036 · FOCUSED PRACTICE
Insert Interval
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 7733 deterministic checks. Learner drafts are not executed.
Understand the problem
Insert one closed interval into a sorted, strictly disjoint list of closed intervals and return the canonical union.
- intervals is a non-null int[][] with 0–100,000 rows. Each row and inserted is a non-null length-two array [start,end] with start≤end and arbitrary signed int coordinates. Both methods throw IllegalArgumentException for malformed rows, malformed inserted, or input that is not sorted and strictly disjoint: previous.end must be less than next.start.
- Endpoints are closed. Touching at one coordinate overlaps and must merge: [1,2] plus [2,3] becomes [1,3]. Point intervals [x,x] are allowed. Return sorted closed intervals with a strict gap between consecutive outputs.
- Preserve the input outer order, all input row values, and inserted. Every returned row is independently allocated and aliases neither any input row nor inserted nor another returned row. inserted may itself reference an existing input row; no caller-owned row is modified.
Examples
Input:
intervals=[[1,3],[6,9]], inserted=[2,5]
Output:[[1,5],[6,9]]The new interval overlaps the first component but ends before the second begins.
Input:
intervals=[[1,2],[4,5],[7,9]], inserted=[2,7]
Output:[[1,9]]Closed endpoints at 2 and 7 join all three components through the inserted range.
Before you start
- Closed versus half-open intervals and compatible endpoints
- Sorting with safe comparators and invariant or exchange proofs
Recognize the structure
The input is already a canonical union, so an insertion can affect only one consecutive overlap component. Preserve the intervals before it, grow one active interval across overlaps, then copy the untouched suffix.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 167/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which old intervals are provably before the insertion?
Hint 2
How far can one growing active end absorb consecutive intervals?
Hint 3
Copy before, merge overlaps, emit once, then copy after.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Append, sort, and merge
Clone every old row and the new row, sort by start with a safe comparator, and merge closed overlaps. For [[1,2],[6,7]] plus [2,6], sorting gives [1,2],[2,6],[6,7]; both touching comparisons merge and produce [1,7]. This O(n log n) baseline ignores the existing input order but gives an easy canonical-union reference.
Improve the baseline
Copy the strict prefix
While an old interval ends before the active inserted start, it cannot overlap this insertion. Copy it to output using a new row.
Absorb one overlap component
While the next old start is at most the active end, replace active boundaries by min(start) and max(end). A growing end may make more consecutive intervals overlap; continue until a strict gap appears.
Emit once and copy the suffix
Append one newly allocated active interval. All remaining old starts are greater than active.end, so clone them in order without further merging.
Why it is correct
Prefix ownership
Every copied prefix interval lies strictly before the original inserted start. Input intervals are already strictly disjoint, so later active growth cannot reach backward across that prefix gap; its earliest possible absorbed start is after the copied prefix end.
Active union invariant
During absorption the active range is exactly the union of inserted and all absorbed intervals, because each new interval intersects it under closed semantics. No holes appear. The first interval with start>active.end ends this component, and all later starts are at least as large.
Canonical completion and identity
The emitted prefix, one active component, and remaining suffix cover exactly the old union plus insertion and remain sorted with strict gaps. Every loop advances i; empty input still emits inserted once. Cloning old rows and allocating the active row preserves caller ownership and output-row independence.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void row(int[] value) {
if (value == null || value.length != 2 || value[0] > value[1]) throw new IllegalArgumentException("closed interval required");
}
private static void validate(int[][] intervals, int[] inserted) {
row(inserted);
for (int i = 0; i < intervals.length; i++) {
row(intervals[i]);
if (i > 0 && intervals[i - 1][1] >= intervals[i][0]) throw new IllegalArgumentException("sorted strictly disjoint input required");
}
}
public static int[][] insert(int[][] intervals, int[] inserted) {
validate(intervals, inserted);
List<int[]> answer = new ArrayList<>();
int i = 0, start = inserted[0], end = inserted[1];
while (i < intervals.length && intervals[i][1] < start) answer.add(intervals[i++].clone());
while (i < intervals.length && intervals[i][0] <= end) {
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i++;
}
answer.add(new int[]{start, end});
while (i < intervals.length) answer.add(intervals[i++].clone());
return answer.toArray(int[][]::new);
}
public static int[][] baseline(int[][] intervals, int[] inserted) {
validate(intervals, inserted);
int[][] sorted = new int[intervals.length + 1][];
for (int i = 0; i < intervals.length; i++) sorted[i] = intervals[i].clone();
sorted[intervals.length] = inserted.clone();
Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
List<int[]> answer = new ArrayList<>();
for (int[] next : sorted) {
if (answer.isEmpty() || answer.getLast()[1] < next[0]) answer.add(next.clone());
else answer.getLast()[1] = Math.max(answer.getLast()[1], next[1]);
}
return answer.toArray(int[][]::new);
}
}
Read the meaningful blocks
Use < before and <= during absorption
Equality is a closed overlap, so the before-phase must not copy a touching interval as a separate component.
Keep active boundaries as local ints
Updating start/end variables avoids modifying inserted or an absorbed source row.
Clone every untouched row too
Returning a source row directly would expose output mutation back to the caller even when the interval values are already correct.
Complexity
O(n) time including validation and all copies. Returned storage is O(n) cells/rows in the worst case; beyond output construction, the scan state is O(1). The ArrayList backing storage is part of assembling the O(n) output and conversion temporarily retains another O(n) reference array.
The sort-and-merge baseline takes O(n log n) time and O(n) copy, sorting, and output storage. Sorting is unnecessary for the optimized API because sorted strictly disjoint input is enforced.
Exact-state walkthroughs
Reveal normal and boundary traces
Bridge several closed components
Input: {"intervals":[[1,2],[4,5],[7,9]],"inserted":[2,7]} · Result: [[1,9]]
Step 1 of 6: Validate canonical input and initialize local active bounds.
Caller rows remain unchanged; only local active bounds may expand.
Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions. The last row is the original inserted interval.
- Row #0:
[1, 2]— next source interval - Row #1:
[4, 5] - Row #2:
[7, 9] - Row #3:
[2, 7]— insertion
- [2, 7]
Empty at this step.
| Variable | Value |
|---|---|
| intervalRows | [[1,2],[4,5],[7,9]] |
| inserted | [2,7] |
| index | 0 |
| activeInterval | [2,7] |
| activeEmitted | false |
| emitted | [] |
| phase | "before" |
| closed | true |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void row(int[] value) { 4 if (value == null || value.length != 2 || value[0] > value[1]) throw new IllegalArgumentException("closed interval required"); 5 } 6 private static void validate(int[][] intervals, int[] inserted) { 7 row(inserted); 8 for (int i = 0; i < intervals.length; i++) { 9 row(intervals[i]); 10 if (i > 0 && intervals[i - 1][1] >= intervals[i][0]) throw new IllegalArgumentException("sorted strictly disjoint input required"); 11 } 12 } 13 public static int[][] insert(int[][] intervals, int[] inserted) { 14 validate(intervals, inserted); 15 List<int[]> answer = new ArrayList<>(); 16 int i = 0, start = inserted[0], end = inserted[1]; 17 while (i < intervals.length && intervals[i][1] < start) answer.add(intervals[i++].clone()); 18 while (i < intervals.length && intervals[i][0] <= end) { 19 start = Math.min(start, intervals[i][0]); 20 end = Math.max(end, intervals[i][1]); 21 i++; 22 } 23 answer.add(new int[]{start, end}); 24 while (i < intervals.length) answer.add(intervals[i++].clone()); 25 return answer.toArray(int[][]::new); 26 } 27 public static int[][] baseline(int[][] intervals, int[] inserted) { 28 validate(intervals, inserted); 29 int[][] sorted = new int[intervals.length + 1][]; 30 for (int i = 0; i < intervals.length; i++) sorted[i] = intervals[i].clone(); 31 sorted[intervals.length] = inserted.clone(); 32 Arrays.sort(sorted, Comparator.comparingInt(value -> value[0])); 33 List<int[]> answer = new ArrayList<>(); 34 for (int[] next : sorted) { 35 if (answer.isEmpty() || answer.getLast()[1] < next[0]) answer.add(next.clone()); 36 else answer.getLast()[1] = Math.max(answer.getLast()[1], next[1]); 37 } 38 return answer.toArray(int[][]::new); 39 } 40 } 41
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate canonical input and initialize local active bounds.
Caller rows remain unchanged; only local active bounds may expand.
- intervalRows
[[1,2],[4,5],[7,9]]- inserted
[2,7]- index
0- activeInterval
[2,7]- activeEmitted
false- emitted
[]- phase
"before"- closed
true
- Absorb one closed overlap into the active union.
The active range is exactly the union of the insertion and consumed overlapping intervals. Equality counts as overlap.
- intervalRows
[[1,2],[4,5],[7,9]]- inserted
[2,7]- index
1- activeInterval
[1,7]- activeEmitted
false- emitted
[]- phase
"absorb"- closed
true
- Absorb one closed overlap into the active union.
The active range is exactly the union of the insertion and consumed overlapping intervals. Equality counts as overlap.
- intervalRows
[[1,2],[4,5],[7,9]]- inserted
[2,7]- index
2- activeInterval
[1,7]- activeEmitted
false- emitted
[]- phase
"absorb"- closed
true
- Absorb one closed overlap into the active union.
The active range is exactly the union of the insertion and consumed overlapping intervals. Equality counts as overlap.
- intervalRows
[[1,2],[4,5],[7,9]]- inserted
[2,7]- index
3- activeInterval
[1,9]- activeEmitted
false- emitted
[]- phase
"absorb"- closed
true
- Emit the completed overlap component once.
The next source start, if present, lies strictly beyond the active end.
- intervalRows
[[1,2],[4,5],[7,9]]- inserted
[2,7]- index
3- activeInterval
[1,9]- activeEmitted
true- emitted
[[1,9]]- phase
"emit"- closed
true
- Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
- result
[[1,9]]
Insert a closed point into an empty union
Input: {"intervals":[],"inserted":[3,3]} · Result: [[3,3]]
Step 1 of 3: Validate canonical input and initialize local active bounds.
Caller rows remain unchanged; only local active bounds may expand.
Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions. The last row is the original inserted interval.
- Row #0:
[3, 3]— insertion
- [3, 3]
Empty at this step.
| Variable | Value |
|---|---|
| intervalRows | [] |
| inserted | [3,3] |
| index | 0 |
| activeInterval | [3,3] |
| activeEmitted | false |
| emitted | [] |
| phase | "before" |
| closed | true |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void row(int[] value) { 4 if (value == null || value.length != 2 || value[0] > value[1]) throw new IllegalArgumentException("closed interval required"); 5 } 6 private static void validate(int[][] intervals, int[] inserted) { 7 row(inserted); 8 for (int i = 0; i < intervals.length; i++) { 9 row(intervals[i]); 10 if (i > 0 && intervals[i - 1][1] >= intervals[i][0]) throw new IllegalArgumentException("sorted strictly disjoint input required"); 11 } 12 } 13 public static int[][] insert(int[][] intervals, int[] inserted) { 14 validate(intervals, inserted); 15 List<int[]> answer = new ArrayList<>(); 16 int i = 0, start = inserted[0], end = inserted[1]; 17 while (i < intervals.length && intervals[i][1] < start) answer.add(intervals[i++].clone()); 18 while (i < intervals.length && intervals[i][0] <= end) { 19 start = Math.min(start, intervals[i][0]); 20 end = Math.max(end, intervals[i][1]); 21 i++; 22 } 23 answer.add(new int[]{start, end}); 24 while (i < intervals.length) answer.add(intervals[i++].clone()); 25 return answer.toArray(int[][]::new); 26 } 27 public static int[][] baseline(int[][] intervals, int[] inserted) { 28 validate(intervals, inserted); 29 int[][] sorted = new int[intervals.length + 1][]; 30 for (int i = 0; i < intervals.length; i++) sorted[i] = intervals[i].clone(); 31 sorted[intervals.length] = inserted.clone(); 32 Arrays.sort(sorted, Comparator.comparingInt(value -> value[0])); 33 List<int[]> answer = new ArrayList<>(); 34 for (int[] next : sorted) { 35 if (answer.isEmpty() || answer.getLast()[1] < next[0]) answer.add(next.clone()); 36 else answer.getLast()[1] = Math.max(answer.getLast()[1], next[1]); 37 } 38 return answer.toArray(int[][]::new); 39 } 40 } 41
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Validate canonical input and initialize local active bounds.
Caller rows remain unchanged; only local active bounds may expand.
- intervalRows
[]- inserted
[3,3]- index
0- activeInterval
[3,3]- activeEmitted
false- emitted
[]- phase
"before"- closed
true
- Emit the completed overlap component once.
The next source start, if present, lies strictly beyond the active end.
- intervalRows
[]- inserted
[3,3]- index
0- activeInterval
[3,3]- activeEmitted
true- emitted
[[3,3]]- phase
"emit"- closed
true
- Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
- result
[[3,3]]
Test the contract
Input:
intervals=[], inserted=[3,3]
Output:[[3,3]]A closed point interval is valid.
Input:
intervals=[[2,5]], inserted=[3,4]
Output:[[2,5]]Contained insertion changes no covered points.
Input:
intervals=[[3,4]], inserted=[0,1]
Output:[[0,1],[3,4]]Insertion before all old intervals.
Input:
intervals=[[1,2],[2,3]], inserted=[5,6]
Output:IllegalArgumentExceptionInput must already have strict gaps.
Common mistakes and counterexamples
Treat equality as a gap
Counterexample: [[1,2]] plus [2,3] must become [[1,3]].
Use closed-overlap comparisons consistently.
Write expanded bounds into inserted
Counterexample: If inserted aliases an existing input row, this changes caller data and can corrupt later reads.
Use local bounds and allocate the output row.
Apply the linear scan to arbitrary unsorted intervals
Counterexample: [[6,7],[1,2]] violates the ordered-prefix argument.
Reject the precondition violation here or use a separate sort-and-merge API.
Follow-ups
Accept unsorted overlapping input.
Clone all intervals and sort/merge them with the inserted range. The input validation and O(n log n) complexity belong to a broader API; the linear proof depends on canonical input.
Perform repeated insertions.
Repeated array rebuilding costs O(n) per insertion. A balanced ordered structure keyed by start can locate neighbors and merge affected components, but outputting the full union still costs its size.
Switch to half-open ranges.
Decide whether merely adjacent ranges should be coalesced for canonical union representation. Half-open [1,2) and [2,3) do not overlap, though their union can be represented as [1,3). Endpoint overlap and representation policy are separate decisions.