Watch the video solution for Maximize Active Section with Trade II, a hard level problem involving Array, String, Binary Search. This walkthrough by Programming Live with Larry has 426 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a binary string s of length n, where:
'1' represents an active section.'0' represents an inactive section.You can perform at most one trade to maximize the number of active sections in s. In a trade, you:
'1's that is surrounded by '0's to all '0's.'0's that is surrounded by '1's to all '1's.Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a substring s[li...ri].
For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].
Return an array answer, where answer[i] is the result for queries[i].
Note
s[li...ri] as if it is augmented with a '1' at both ends, forming t = '1' + s[li...ri] + '1'. The augmented '1's do not contribute to the final count.
Example 1:
Input: s = "01", queries = [[0,1]]
Output: [1]
Explanation:
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.
Example 2:
Input: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
Output: [4,3,1,1]
Explanation:
Query [0, 3] → Substring "0100" → Augmented to "101001"
Choose "0100", convert "0100" → "0000" → "1111".
The final string without augmentation is "1111". The maximum number of active sections is 4.
Query [0, 2] → Substring "010" → Augmented to "10101"
Choose "010", convert "010" → "000" → "111".
The final string without augmentation is "1110". The maximum number of active sections is 3.
Query [1, 3] → Substring "100" → Augmented to "11001"
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.
Query [2, 3] → Substring "00" → Augmented to "1001"
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.
Example 3:
Input: s = "1000100", queries = [[1,5],[0,6],[0,4]]
Output: [6,7,2]
Explanation:
Query [1, 5] → Substring "00010" → Augmented to "1000101"
Choose "00010", convert "00010" → "00000" → "11111".
The final string without augmentation is "1111110". The maximum number of active sections is 6.
Query [0, 6] → Substring "1000100" → Augmented to "110001001"
Choose "000100", convert "000100" → "000000" → "111111".
The final string without augmentation is "1111111". The maximum number of active sections is 7.
Query [0, 4] → Substring "10001" → Augmented to "1100011"
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 2.
Example 4:
Input: s = "01010", queries = [[0,3],[1,4],[1,3]]
Output: [4,4,2]
Explanation:
Query [0, 3] → Substring "0101" → Augmented to "101011"
Choose "010", convert "010" → "000" → "111".
The final string without augmentation is "11110". The maximum number of active sections is 4.
Query [1, 4] → Substring "1010" → Augmented to "110101"
Choose "010", convert "010" → "000" → "111".
The final string without augmentation is "01111". The maximum number of active sections is 4.
Query [1, 3] → Substring "101" → Augmented to "11011"
Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 2.
Constraints:
1 <= n == s.length <= 1051 <= queries.length <= 105s[i] is either '0' or '1'.queries[i] = [li, ri]0 <= li <= ri < nProblem Overview: You are given an array or binary string representing active and inactive sections. A trade operation allows changing specific segments to improve the number of active positions. The goal is to perform trades optimally so the longest continuous active section becomes as large as possible.
Approach 1: Brute Force Simulation (O(n^3) time, O(1) space)
Start by enumerating all possible trade operations and apply them to the array. After each simulated trade, scan the entire array to compute the longest contiguous active segment. This requires nested iteration over possible trade boundaries and another pass to measure the active stretch. The method is straightforward but extremely slow for large inputs because every trade candidate requires rebuilding and scanning the array.
Approach 2: Prefix Analysis + Binary Search (O(n log n) time, O(n) space)
Precompute prefix counts of inactive positions so you can quickly evaluate how many changes are required in any subarray. Then apply binary search on the answer: guess the maximum possible active section length and check whether a trade configuration can achieve it. Each feasibility check slides a window and uses prefix differences to determine if the required trades fit within constraints. This approach avoids trying every trade explicitly and instead searches over valid lengths.
Approach 3: Segment Tree Optimization (O(n log n) time, O(n) space)
Build a segment tree that stores information about active streaks in each interval: prefix active length, suffix active length, and maximum active segment inside the range. When evaluating potential trades, update affected segments and query the tree to compute the resulting maximum active section. The tree allows fast merges of segment information, making it efficient when multiple trade evaluations are required.
The segment structure typically stores values like maxActive, prefixActive, and suffixActive so two child segments can be combined in constant time. This pattern appears frequently in interval problems involving contiguous ranges and is common in advanced array manipulation tasks.
Recommended for interviews: Start by describing the brute force idea to show you understand the problem space. Then move quickly to the binary search + prefix feasibility approach, which significantly reduces the search space. If the problem requires frequent dynamic updates or complex range evaluation, the segment tree solution demonstrates deeper algorithmic skill and is the approach most senior interviewers expect for hard interval problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Trade Simulation | O(n^3) | O(1) | Useful for reasoning about the problem or verifying small inputs |
| Prefix Counts + Binary Search | O(n log n) | O(n) | General solution when checking feasibility of segment length efficiently |
| Segment Tree Range Optimization | O(n log n) | O(n) | Best when multiple range updates or queries are needed to evaluate trades |