Skip to main content
Talentd

Minimize Connected Groups by Inserting Interval - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchSliding WindowSorting8 min readAsked at: De Shaw
Practice this problem

Problem Statement

You are given a 2D array intervals, where intervals[i] = [starti, endi] represents the start and the end of interval i. You are also given an integer k.

You must add exactly one new interval [startnew, endnew] to the array such that:

  • The length of the new interval, endnew - startnew, is at most k.
  • After adding, the number of connected groups in intervals is minimized.

A connected group of intervals is a maximal collection of intervals that, when considered together, cover a continuous range from the smallest point to the largest point with no gaps between them. Here are some examples:

  • A group of intervals [[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps.
  • However, a group of intervals [[1, 2], [3, 4]] is not connected because the segment (2, 3) is not covered.

Return the minimum number of connected groups after adding exactly one new interval to the array.

 

Example 1:

Input: intervals = [[1,3],[5,6],[8,10]], k = 3

Output: 2

Explanation:

After adding the interval [3, 5], we have two connected groups: [[1, 3], [3, 5], [5, 6]] and [[8, 10]].

Example 2:

Input: intervals = [[5,10],[1,1],[3,3]], k = 1

Output: 3

Explanation:

After adding the interval [1, 1], we have three connected groups: [[1, 1], [1, 1]], [[3, 3]], and [[5, 10]].

 

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i] == [starti, endi]
  • 1 <= starti <= endi <= 109
  • 1 <= k <= 109

Approach Overview

Problem Overview: You are given several intervals that may form multiple disconnected groups. You can insert one additional interval. The goal is to place this interval so that it connects as many existing groups as possible, minimizing the final number of connected components.

Approach 1: Brute Force Gap Merging (O(n^2) time, O(1) space)

Start by sorting intervals by their starting position using sorting. Compute the gaps between consecutive merged intervals. Try placing the new interval so that it bridges different combinations of gaps and simulate how many groups merge. For every starting interval, expand forward while the inserted interval can still cover the span needed to connect them. This approach works conceptually but becomes quadratic because each starting point may scan many following intervals.

Approach 2: Sorting + Binary Search (O(n log n) time, O(n) space)

Sort intervals first, then merge overlapping ones to determine the true connected groups. After merging, compute the gaps between consecutive groups. If an inserted interval can cover multiple consecutive gaps, those groups collapse into one component. For each group i, use binary search to find the farthest group j such that the total distance from the end of group i to the start of group j can be covered by the inserted interval. The number of groups merged equals j - i. Track the maximum merge possible and subtract it from the original group count.

Approach 3: Sorting + Sliding Window (O(n log n) time, O(n) space)

After sorting and merging intervals, treat the problem as covering consecutive gaps with a single interval of fixed reach. Maintain a window of groups and track the span between the first group's end and the current group's start. If that span exceeds the allowed coverage, move the left pointer forward. This two-pointer technique from sliding window keeps the largest set of groups that can be connected by one inserted interval. The result is the total groups minus the maximum window size reduction.

Recommended for interviews: The expected solution is Sorting + Binary Search or a sliding window after sorting. The brute-force gap simulation demonstrates understanding of how intervals merge, but the optimized method shows you can translate the problem into a range search over sorted intervals and reduce it to O(n log n).

Solution

First, we sort the given set of intervals intervals by their left endpoints, then merge all overlapping intervals to obtain a new set of intervals merged.

We can then set the initial answer to the length of merged.

Next, we enumerate each interval [_, e] in merged. Using binary search, we find the first interval in merged whose left endpoint is greater than or equal to e + k + 1, and let its index be j. We can then update the answer as ans = min(ans, |merged| - (j - i - 1)).

Finally, we return the answer ans.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of intervals.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Gap MergingO(n^2)O(1)Useful for understanding how interval gaps combine and verifying correctness on small inputs
Sorting + Binary SearchO(n log n)O(n)Best general solution when intervals must be sorted and the farthest connectable group is searched efficiently
Sorting + Sliding WindowO(n log n)O(n)Clean implementation after sorting; ideal when consecutive gaps are processed with two pointers

Video Solution

LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize Connected Groups by Inserting Interval easy or hard?
This problem is generally rated Medium difficulty. The main challenge is recognizing that inserting an interval effectively covers gaps between sorted groups, which converts the problem into a search over consecutive intervals using binary search or sliding window techniques.
Minimize Connected Groups by Inserting Interval Python/Java solution
Typical implementations first sort intervals, merge overlaps, then compute how many groups can be connected by one inserted interval. The same algorithm works across Python, Java, C++, Go, and TypeScript with O(n log n) time and O(n) auxiliary space.
How to solve Minimize Connected Groups by Inserting Interval in O(n)?
A near linear pass is possible after sorting the intervals. Once intervals are sorted and merged, a sliding window can scan consecutive groups while tracking the span between the first and last group in the window. If that span exceeds what the inserted interval can cover, move the left pointer forward. The scanning step itself is O(n), though sorting still costs O(n log n).
What is the best approach for Minimize Connected Groups by Inserting Interval?
Sorting the intervals and then using binary search or a sliding window is the most efficient approach. After merging overlapping intervals, compute the gaps between groups and determine how many consecutive groups can be connected by inserting a single interval. This reduces the problem to searching the largest connectable range. The overall complexity is O(n log n) due to sorting and binary search.
Is Minimize Connected Groups by Inserting Interval asked at Google/Amazon/Meta?
Interval merging, gap analysis, and sliding window patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem test whether you can transform interval connectivity problems into range or gap optimization problems.
What data structure is used in Minimize Connected Groups by Inserting Interval?
The core structures are arrays or lists of intervals combined with sorting. Binary search is used to locate the farthest reachable interval efficiently, and a sliding window with two pointers can optimize consecutive gap processing.
What is the time complexity of Minimize Connected Groups by Inserting Interval?
The optimal solution runs in O(n log n) time. Sorting the intervals dominates the complexity, while the binary search or sliding window step processes the merged groups efficiently. Space complexity is typically O(n) to store merged intervals or gap information.

Ready to solve this problem?

Practice Minimize Connected Groups by Inserting Interval with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Intervals