Skip to main content
Talentd

Video Stitching - Solution & Explanation

MediumArrayDynamic ProgrammingGreedy19 min readAsked at: Google, Anduril, Verily
Practice this problem

Problem Statement

You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.

Each video clip is described by an array clips where clips[i] = [starti, endi] indicates that the ith clip started at starti and ended at endi.

We can cut these clips into segments freely.

  • For example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.

 

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].

Example 3:

Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].

 

Constraints:

  • 1 <= clips.length <= 100
  • 0 <= starti <= endi <= 100
  • 1 <= time <= 100

Approach Overview

Problem Overview: You receive several video clips where each clip is represented as [start, end]. The goal is to stitch together the minimum number of clips so the entire interval [0, time] is covered. Clips can overlap and can be cut into smaller segments.

Approach 1: Greedy Algorithm (O(n log n) time, O(1) space)

The greedy strategy works similarly to the classic interval coverage problem. First, sort the clips by their start time. Then iterate through them while tracking the farthest point you can reach with clips that begin before or at the current coverage boundary. Each time the current segment ends, select the clip that extends coverage the farthest. This is conceptually similar to the jump expansion technique used in interval coverage problems. The key insight: whenever multiple clips overlap the current boundary, always choose the one with the maximum end value. Sorting costs O(n log n), and the single pass through the clips keeps the rest of the work linear.

This approach fits naturally under Greedy strategy because each decision locally maximizes the reachable interval. Once a segment is chosen, you never need to reconsider earlier clips.

Approach 2: Dynamic Programming (O(n * T) time, O(T) space)

The dynamic programming approach builds a table where dp[t] represents the minimum number of clips needed to cover the interval [0, t]. Initialize all values with a large number and set dp[0] = 0. For each clip [start, end], update all reachable times between start and end. The transition looks like dp[i] = min(dp[i], dp[start] + 1) for all i in that range. This effectively tries every clip as a possible extension of an already covered segment.

This method models the problem as incremental coverage and is easier to reason about if you're comfortable with Dynamic Programming. However, it performs more updates than the greedy method and becomes slower when the target time T grows.

Recommended for interviews: The greedy solution is the expected answer in most interviews because it reduces the problem to interval expansion with optimal local choices. Interviewers typically want to see you recognize the similarity to interval covering or jump-style problems on arrays. Starting with a brute-force or DP explanation shows understanding, but arriving at the greedy optimization demonstrates stronger algorithmic intuition with Array interval problems.

Approach 1: Greedy Algorithm

The greedy approach involves sorting the clips based on their start times, and then iteratively selecting clips that extend the coverage as far as possible. Prioritize clips with earlier start times and check how far they can extend the current coverage. If you ever get stuck where no clips can extend the coverage, it's impossible to cover the entire event, otherwise, continue until the end is covered.

This C implementation uses a greedy approach. The clips are first sorted by their start time. The code iterates over the sorted clips, updating the farthest point that can be reached. If it can't extend the coverage, the function returns -1. Otherwise, it returns the number of clips used.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting of the clips.
Space Complexity: O(1), uses a constant amount of extra space.

Try this approach in the editor β†’

Approach 2: Dynamic Programming

In the dynamic programming approach, an array dp[] is used where dp[i] indicates the minimum number of clips needed to cover up to the i-th second. Initialize this array with a large number except for dp[0] = 0, then iterate over each second and find the minimal solution by iterating over the clips that take part in that segment.

This C solution uses a dynamic programming table (dp) to store the minimum number of clips needed to cover each time unit up to the given 'time'. Each dp[t] is updated by iterating over each available clip and checking if it participates in forming the segment [clips[i][0], clips[i][1]].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * time), where n is the number of clips and time is the duration.
Space Complexity: O(time), additional space to store dp array.

Try this approach in the editor β†’

Approach 3: Greedy

Note that if there are multiple sub-intervals with the same starting point, it is optimal to choose the one with the largest right endpoint.

Therefore, we can preprocess all sub-intervals. For each position i, calculate the largest right endpoint among all sub-intervals starting at i, and record it in the array last[i].

We define a variable mx to represent the farthest position that can currently be reached, a variable ans to represent the current minimum number of sub-intervals needed, and a variable pre to represent the right endpoint of the last used sub-interval.

Next, we start enumerating all positions i from 0, using last[i] to update mx. If after updating, mx = i, it means that the next position cannot be covered, so the task cannot be completed, return -1.

At the same time, we record the right endpoint pre of the last used sub-interval. If pre = i, it means that a new sub-interval needs to be used, so we add 1 to ans and update pre to mx.

After the traversal is over, return ans.

The time complexity is O(n+m), and the space complexity is O(m). Where n and m are the lengths of the clips array and the value of time, respectively.

Similar problems:

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Greedy Algorithm

Time Complexity: O(n log n), due to sorting of the clips.
Space Complexity: O(1), uses a constant amount of extra space.

Dynamic Programming

Time Complexity: O(n * time), where n is the number of clips and time is the duration.
Space Complexity: O(time), additional space to store dp array.

Greedyβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Interval ExpansionO(n log n)O(1)Best general solution. Efficient when clips must be merged to cover an interval.
Dynamic ProgrammingO(n * T)O(T)Useful for reasoning about incremental coverage when time range is small.

Video Solution

θŠ±θŠ±ι…± LeetCode 1024. Video Stitching - εˆ·ι’˜ζ‰Ύε·₯作 EP248 β€’ Hua Hua β€’ 5,032 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Video Stitching easy or hard?
Video Stitching is considered a medium difficulty problem. The challenge lies in recognizing that it reduces to an interval coverage greedy strategy rather than trying every combination of clips. Once the interval expansion idea is clear, the implementation becomes straightforward.
How to solve Video Stitching in O(n)?
A near O(n) greedy scan is possible if clips are preprocessed or stored by start time similar to the Jump Game approach. Build an array that tracks the farthest reachable end for each start point, then expand coverage step by step. This avoids sorting and keeps the traversal linear with respect to the target time.
What is the best approach for Video Stitching?
The greedy interval expansion approach is the most efficient solution. Sort clips by start time and always choose the clip that extends the current coverage the farthest. This guarantees the minimum number of clips while running in O(n log n) time due to sorting and O(1) extra space.
What data structure is used in Video Stitching?
The problem primarily uses arrays and interval processing. The greedy solution relies on sorting and sequential scanning of intervals, while the dynamic programming solution maintains a DP array that tracks the minimum clips needed to cover each time point.
What is the time complexity of Video Stitching?
The optimal greedy solution runs in O(n log n) time because the clips must first be sorted by start time. After sorting, a single linear pass determines the minimum clips required. Space complexity remains O(1) since only a few variables track the current and farthest coverage.
Video Stitching Python or Java solution approach?
Both Python and Java implementations typically follow the same greedy pattern: sort clips by start time, iterate through overlapping clips, and update the farthest reachable endpoint. The algorithmic complexity remains O(n log n) with constant extra space regardless of language.
Is Video Stitching asked at Google, Amazon, or Meta?
Video Stitching is a common interval coverage problem frequently appearing in interviews at large tech companies. Variants of interval merging and greedy coverage are known to appear at companies like Google, Amazon, and Meta because they test greedy reasoning and array processing.

Ready to solve this problem?

Practice Video Stitching with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays