Minimum Time to Remove All Cars Containing Illegal Goods - Solution & Explanation
Problem Statement
You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the ith car does not contain illegal goods and s[i] = '1' denotes that the ith car does contain illegal goods.
As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:
- Remove a train car from the left end (i.e., remove
s[0]) which takes 1 unit of time. - Remove a train car from the right end (i.e., remove
s[s.length - 1]) which takes 1 unit of time. - Remove a train car from anywhere in the sequence which takes 2 units of time.
Return the minimum time to remove all the cars containing illegal goods.
Note that an empty sequence of cars is considered to have no cars containing illegal goods.
Example 1:
Input: s = "1100101" Output: 5 Explanation: One way to remove all the cars containing illegal goods from the sequence is to - remove a car from the left end 2 times. Time taken is 2 * 1 = 2. - remove a car from the right end. Time taken is 1. - remove the car containing illegal goods found in the middle. Time taken is 2. This obtains a total time of 2 + 1 + 2 = 5. An alternative way is to - remove a car from the left end 2 times. Time taken is 2 * 1 = 2. - remove a car from the right end 3 times. Time taken is 3 * 1 = 3. This also obtains a total time of 2 + 3 = 5. 5 is the minimum time taken to remove all the cars containing illegal goods. There are no other ways to remove them with less time.
Example 2:
Input: s = "0010" Output: 2 Explanation: One way to remove all the cars containing illegal goods from the sequence is to - remove a car from the left end 3 times. Time taken is 3 * 1 = 3. This obtains a total time of 3. Another way to remove all the cars containing illegal goods from the sequence is to - remove the car containing illegal goods found in the middle. Time taken is 2. This obtains a total time of 2. Another way to remove all the cars containing illegal goods from the sequence is to - remove a car from the right end 2 times. Time taken is 2 * 1 = 2. This obtains a total time of 2. 2 is the minimum time taken to remove all the cars containing illegal goods. There are no other ways to remove them with less time.
Constraints:
1 <= s.length <= 2 * 105s[i]is either'0'or'1'.
Approach Overview
Problem Overview: You receive a binary string where '1' represents a car carrying illegal goods. Removing a car from the left or right end costs 1, while removing a specific illegal car in the middle costs 2. The goal is to remove all '1' cars with the minimum total time.
Approach 1: Prefix and Suffix Counting (O(n) time, O(n) space)
This method treats the problem as a dynamic programming scan across the string. Build a prefix array where left[i] stores the minimum cost to remove all illegal cars from index 0..i. For each position, either remove the current illegal car individually (left[i-1] + 2) or remove the entire prefix from the left side (i + 1). A similar suffix array computes the cost of removing illegal cars from i..n-1. Once both arrays are built, iterate over every split point and combine left[i] + right[i+1]. This captures strategies where part of the string is removed from the left and the remainder from the right. The approach is intuitive and easy to reason about during interviews because it explicitly models costs from both directions.
Approach 2: Greedy Counting with Two Pointer Technique (O(n) time, O(1) space)
The optimal solution compresses the DP idea into a single pass using a greedy running cost. Traverse the string from left to right while maintaining the minimum cost to clear all illegal cars up to the current index. When you encounter a '1', you have two choices: remove it individually (currentCost + 2) or remove the entire prefix from the left (i + 1). Track the minimum of these options. At each step, combine the prefix cost with the cost of removing the remaining suffix by popping cars from the right (n - i - 1). This effectively simulates a two-pointer strategy where the left scan determines prefix removal cost and the right boundary represents future removals. The result is the minimum total time seen during the scan.
Recommended for interviews: The greedy single-pass approach is what most interviewers expect. It reduces the prefix–suffix DP idea to O(1) space while keeping the same O(n) runtime. Showing the prefix/suffix DP first demonstrates clear reasoning about the cost structure, then optimizing it to the greedy scan shows strong algorithmic intuition.
Approach 1: Prefix and Suffix Counting
This approach involves counting the number of illegal cars ('1's) from the start of the string (prefix) and from the end (suffix). For each possible position, we calculate the minimum time required to remove all illegal goods up to that position using prefix and suffix data.
The algorithm first computes prefix sums for '1's, which represent the cumulative number of illegal cars encountered from the start of the string to each position. Similarly, suffix sums are calculated to count '1's from the end of the string to each position. By checking each split of the string, we determine the total time required to remove all illegal goods up to each position and select the minimum.
Complexity
Time Complexity: O(n), where n is the length of the string, due to the creation of prefix and suffix arrays.
Space Complexity: O(n) due to the storage of prefix and suffix arrays.
Approach 2: Greedy Counting with Two Pointer Technique
This approach uses a greedy counting strategy with a two-pointer technique to efficiently remove '1's. It traverses the string from both ends simultaneously, accumulating time until all '1's are removed.
The two-pointer strategy effectively narrows down the portion of the string containing '1's by skipping initial '0's. By making greedy choices, we incrementally account for time whenever a '1' is encountered. The process ends when the left pointer surpasses the right pointer.
Code
Java
JavaScript
Complexity
Time Complexity: O(n) with a single traversal of the string using two pointers.
Space Complexity: O(1) as no additional structures are used beyond fixed pointers.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Counting | Time Complexity: O(n), where n is the length of the string, due to the creation of prefix and suffix arrays. |
| Greedy Counting with Two Pointer Technique | Time Complexity: O(n) with a single traversal of the string using two pointers. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Counting | O(n) | O(n) | Best for understanding the cost structure and explaining the dynamic programming reasoning clearly. |
| Greedy Counting with Two Pointer Technique | O(n) | O(1) | Preferred in interviews and production since it compresses the DP idea into a single linear pass with constant space. |
Video Solution
MultiStaged DP | Leetcode Weekly Episode 3 | Leetcode 2167 | Dynamic Programming • Vivek Gupta • 3,701 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Minimum Time to Remove All Cars Containing Illegal Goods easy or hard?
Minimum Time to Remove All Cars Containing Illegal Goods Python/Java solution
How to solve Minimum Time to Remove All Cars Containing Illegal Goods in O(n)?
What is the best approach for Minimum Time to Remove All Cars Containing Illegal Goods?
Is Minimum Time to Remove All Cars Containing Illegal Goods asked at Google/Amazon/Meta?
What data structure is used in Minimum Time to Remove All Cars Containing Illegal Goods?
What is the time complexity of Minimum Time to Remove All Cars Containing Illegal Goods?
Ready to solve this problem?
Practice Minimum Time to Remove All Cars Containing Illegal Goods with our built-in code editor and test cases.
Practice on FleetCode