Skip to content

Volume ITechnology

4.27.1 — Insert Interval ​

LeetCode 57 · Medium · ★ Blind 75

The problem ​

Given a list of non-overlapping intervals sorted by start, insert a new interval and merge where necessary. The result must stay sorted and non-overlapping.

Restating the Problem: You have a perfectly organized schedule of non-overlapping events. Suddenly, a new event is added. Your job is to insert this new event into the schedule. If it overlaps with any existing events, you must merge them into one continuous block so that the final schedule remains conflict-free.

  • Constraints to note: The number of intervals n is up to 10^4. They are already sorted, which is a massive hint to aim for an O(n) solution.
  • Edge cases: The new interval might come completely before all others, completely after all others, or it might swallow all existing intervals entirely.
intervals = [[1,3],[6,9]], newInterval = [2,5]   →  [[1,5],[6,9]]
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
                                                 →  [[1,2],[3,10],[12,16]]

The brute force, and where it wastes work ​

A naive approach would be to simply append the newInterval to the end of the intervals array, and then run a standard "Merge Intervals" algorithm. This involves sorting the entire combined array, which takes O(n \log n) time. While O(n \log n) is acceptable for n=10^4, it completely ignores the fact that the initial array is already sorted. We can do better by doing it in a single pass.

The pattern ​

The input is already sorted, which is the gift — no sorting step, so this is O(n) rather than O(n \log n).

Walk the list once, and every interval falls into exactly one of three groups:

  1. Ends before the new one starts — no overlap, copy it out.
  2. Overlaps the new one — absorb it into the new interval by widening.
  3. Starts after the new one ends — no overlap, copy it out.

Because the list is sorted, the three groups appear in exactly that order, so three sequential loops handle them with no conditionals inside.

The overlap test ​

Two intervals [a, b] and [c, d] overlap when:

a \le d \ \text{and}\ c \le b

Each starts before the other ends. Worth memorising in that form, because it is the cleanest statement and it generalises.

It is often easier to test the negation: they do not overlap when b < c or d < a — one finishes entirely before the other begins. That is what the first and third loops below check.

Touching counts as overlapping here. [1,3] and [3,5] merge into [1,5], because the problem treats them as adjacent. Some problems do not — always check, because it decides whether the comparison is < or <=.

The solution ​

python
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []  # (1)
        i, n = 0, len(intervals)
        start, end = newInterval  # (2)

        # 1. everything entirely before the new interval
        while i < n and intervals[i][1] < start:  # (3)
            result.append(intervals[i])
            i += 1

        # 2. everything that overlaps — widen the new interval to swallow it
        while i < n and intervals[i][0] <= end:  # (4)
            start = min(start, intervals[i][0])  # (5)
            end = max(end, intervals[i][1])  # (6)
            i += 1
        result.append([start, end])  # (7)

        # 3. everything entirely after
        while i < n:  # (8)
            result.append(intervals[i])
            i += 1

        return result
ts
function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];  // (1)
  let i = 0;
  const n = intervals.length;
  let [start, end] = newInterval;  // (2)

  while (i < n && intervals[i][1] < start) result.push(intervals[i++]);  // (3)

  while (i < n && intervals[i][0] <= end) {  // (4)
    start = Math.min(start, intervals[i][0]);  // (5)
    end = Math.max(end, intervals[i][1]);  // (6)
    i++;
  }
  result.push([start, end]);  // (7)

  while (i < n) result.push(intervals[i++]);  // (8)

  return result;
}

Line by line ​

The list is already sorted by start and has no overlaps. That lets us split it into three parts in one walk.

(1) The answer, and a position i that walks the list once.

(2) The new interval's ends. They may grow as it swallows overlapping intervals.

(3) Part one: every interval that ends before the new one starts. It cannot overlap, so copy it straight across.

(4) Part two: every interval that starts before the new one ends. These overlap the new interval. Because part one already removed everything that ends too early, "starts no later than end" is enough to mean "overlaps".

(5) and (6) Grow the new interval to cover each one it swallows: the earlier start and the later end.

(7) Add the grown interval, exactly once.

(8) Part three: everything left starts after the new interval ends. Copy it across.

Three loops, no branching. Each loop handles one group, and the sorted order guarantees they run in sequence. Trying to do it in one loop with an if/elif/else is possible and much harder to keep straight.

The merged interval is appended after the second loop, not inside it — you only know its final extent once every overlapping interval has been absorbed.

intervals[i][0] <= end uses <= because touching intervals merge here.

Code Walkthrough:

  • Initialization: We prepare a result list and track our current index i. We also unpack start and end from the newInterval.
  • Phase 1 (Before): We loop as long as the current interval ends before our new interval starts (intervals[i][1] < start). These are strictly earlier, so we append them directly to result.
  • Phase 2 (Overlap): We loop as long as the current interval starts at or before our new interval ends (intervals[i][0] <= end). This means they overlap or touch. We continuously merge them by updating start to the minimum of both starts, and end to the maximum of both ends. Once this loop finishes, the fully expanded new interval is ready, and we append it to result.
  • Phase 3 (After): We append any remaining intervals. Since they start strictly after our new interval ends, no further merging is needed.

The new interval is appended even if nothing overlapped, which is what handles insertion into a gap.

Trace ​

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new [4,8].

  • Loop 1: [1,2] ends at 2 < 4 → copied.
  • Loop 2: [3,5] starts at 3 ≤ 8 → merge, now [3,8]. [6,7] starts at 6 ≤ 8 → merge, still [3,8]. [8,10] starts at 8 ≤ 8 → merge, now [3,10]. [12,16] starts at 12 > 10 → stop.
  • Append [3,10].
  • Loop 3: [12,16] copied.

Result [[1,2],[3,10],[12,16]] ✓.

Edge cases ​

  • An empty list. The new interval is the whole answer.
  • The new interval goes before everything, or after everything. Part two adds it with no merging.
  • The new interval swallows every interval. Part one and part three are empty.
  • Touching ends, like [1, 2] and a new [2, 3]. They merge, because line (4) uses <=.

Complexity ​

  • Time Complexity: O(n). Even though there are three while loops, the index i only moves forward and each interval is processed exactly once. Thus, the total work is strictly proportional to n.
  • Space Complexity: O(n) to store the output array. No auxiliary space beyond variables is used.

Compare with the alternative of appending the new interval, re-sorting, and merging — O(n \log n). The sorted input is what buys the linear time, and saying so shows you noticed the constraint.

Where this goes next ​

  • Merge Intervals — no new interval, but the input is unsorted, so you sort first and then run the same merging loop. 4.27.2.
  • Interval List Intersections — two sorted lists, walked with two pointers, keeping the overlap of each pair.
  • Calendar booking (LeetCode 729, 731, 732) — repeated insertions with overlap rules, where a balanced tree or an ordered map keeps each insertion O(\log n) instead of O(n). That is the natural follow-up when insertions are frequent.

What the interviewer will push on ​

"State the overlap condition." a <= d and c <= b. Have it ready.

"Do touching intervals merge?" Ask. It changes < to <=, and it is a genuine ambiguity in most problem statements.

"Why three loops?" The sorted order puts the three groups in sequence, so no interleaved conditionals are needed.

"Why is this O(n) and Merge Intervals O(n \log n)?" The input here is already sorted.

"What if you had to insert many intervals?" Repeated O(n) insertions become O(nk). Switch to an ordered map or a balanced tree for O(\log n) per insertion.

One thing to volunteer: name the three groups before writing anything. This problem is easy with the structure stated and fiddly without it.

Next: 4.27.2 Merge Intervals — the same merging, with the sort you have to add yourself.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet