Insert Interval
Mahabharata — Krishna's Emergency Deployment — Inserting Arjuna's Regiment Into the Existing Formation
नवो योधः आगच्छति — पूर्वाणि व्यूहान् परिशोधयेत्। यत्र मिलेत् तत्र एकं कुर्यात् — यत्र न तत्र स्थापयेत्॥
*A new warrior arrives — adjust the existing formations. Where he overlaps, merge into one; where he does not, place him separately.*
The Story
The battle formation was already set: `[[1,2],[3,5],[6,7],[8,10],[12,16]]` — sorted, non-overlapping intervals. Krishna decided to insert Arjuna's regiment at position `[4,8]` mid-battle. The existing array was already sorted; only the new interval needed to be integrated.
"Three phases," Krishna announced: 1. Add all intervals that END before the new interval STARTS (no overlap possible): `end < newStart` 2. Merge all intervals that OVERLAP with the new interval (either contains it or is contained): `start <= newEnd` 3. Add all remaining intervals unchanged
Tracing `[[1,2],[3,5],[6,7],[8,10],[12,16]]`, newInterval=[4,8]:
Phase 1 (end < 4): [1,2] → add. [3,5]: end=5 >= 4, stop. Phase 2 (start <= 8): [3,5] overlaps → expand new to [min(4,3), max(8,5)]=[3,8]. [6,7] overlaps → [3,max(8,7)]=[3,8]. [8,10] overlaps (start=8<=8) → [3,max(8,10)]=[3,10]. [12,16]: start=12>8 → stop. Phase 3: add [12,16].
Result: `[[1,2],[3,10],[12,16]]`
"Unlike mi-1, no sorting needed," Krishna noted. "The input is already sorted. We just find where the new interval fits and merge everything it touches in one pass. O(n) time."
Arjuna's regiment was seamlessly integrated. The battle formation adapted without disruption.
The Commander's First Instinct
Add the new interval to the array, sort everything, then run mi-1's merge algorithm.
public int[][] insertBruteForce(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort((a,b) -> a[0]-b[0]);
// Now apply mi-1 merge
List<int[]> res = new ArrayList<>();
for (int[] iv : list) {
if (res.isEmpty() || res.get(res.size()-1)[1] < iv[0]) res.add(iv);
else res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], iv[1]);
}
return res.toArray(new int[0][]);
}Krishna's Three-Phase Wisdom
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0, n = intervals.length;
// Phase 1: intervals ending before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) result.add(intervals[i++]);
// Phase 2: merge all overlapping
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
// Phase 3: remaining intervals
while (i < n) result.add(intervals[i++]);
return result.toArray(new int[0][]);
}Step-by-Step Walkthrough
intervals=[[1,3],[6,9]], new=[2,5] Phase1: [1,3]: end=3 >= 2 → stop. i=0 Phase2: [1,3]: start=1<=5 → new=[min(2,1),max(5,3)]=[1,5]. i=1 [6,9]: start=6>5 → stop. Add [1,5]. Phase3: add [6,9]. Result: [[1,5],[6,9]] ✅
Deep Insight
**Why O(n) unlike mi-1's O(n log n)?** The input is already sorted and non-overlapping. We don't need to sort — just three linear passes over the array.
**The overlap condition in Phase 2:** `intervals[i][0] <= newInterval[1]` — current interval starts at or before the new one ends (they overlap or touch). This is the mirror of Phase 1's termination.
**Edge cases:** - New interval entirely before all existing: only Phase 3 runs - New interval entirely after all existing: only Phase 1 + add - New interval engulfs everything: all merge into one in Phase 2
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Add + sort + merge |
| Optimal | O(n) | O(n) | Three linear passes, no sorting needed |
Pattern Recognition
✅ Insert into sorted non-overlapping intervals ✅ Three phases: before / overlapping / after ✅ O(n) — no sorting needed ✅ Merge by expanding newInterval during phase 2 **LeetCode Trigger Phrases:** → "insert interval into sorted non-overlapping list" → "insert and merge if necessary" → "sorted intervals" + insert
Bhagavad Gita 4.7
यदा यदा हि धर्मस्य ग्लानिर्भवति भारत। अभ्युत्थानमधर्मस्य तदात्मानं सृजाम्यहम्॥
Whenever there is a decline of dharma and rise of adharma, O Bharata, then I manifest Myself.
Connection: Krishna's emergency insertion into the battle is mirrored by this algorithm: when a new force (interval) enters an existing ordered system, it is merged with precisely those elements it overlaps, and placed exactly where it fits among those it doesn't. The divine doesn't disrupt the entire order — it integrates seamlessly, adjusting only what requires adjustment, leaving everything else undisturbed.