Skip to main content
Talentd

Maximize Active Section with Trade II - Solution & Explanation

HardArrayStringBinary SearchSegment Tree7 min read
Practice this problem

Problem Statement

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:

  • Convert a contiguous block of '1's that is surrounded by '0's to all '0's.
  • Afterward, convert a contiguous block of '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

  • For each query, treat 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.
  • The queries are independent of each other.

 

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 <= 105
  • 1 <= queries.length <= 105
  • s[i] is either '0' or '1'.
  • queries[i] = [li, ri]
  • 0 <= li <= ri < n

Approach Overview

Problem 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.

Solution

Code

Rust

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Trade SimulationO(n^3)O(1)Useful for reasoning about the problem or verifying small inputs
Prefix Counts + Binary SearchO(n log n)O(n)General solution when checking feasibility of segment length efficiently
Segment Tree Range OptimizationO(n log n)O(n)Best when multiple range updates or queries are needed to evaluate trades

Video Solution

Maximize Active Section with Trade II | LeetCode 3501 - Python • impoldev • 630 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximize Active Section with Trade II easy or hard?
Maximize Active Section with Trade II is considered a Hard problem because it combines multiple advanced ideas such as binary search on the answer, contiguous segment evaluation, and sometimes segment tree range aggregation. Efficient reasoning about intervals and feasibility checks is required.
Maximize Active Section with Trade II Python/Java solution
Python, Java, C++, and Go implementations usually follow the same structure: compute prefix statistics, binary search the maximum achievable segment length, and validate each candidate using sliding window or segment tree queries. The algorithm remains O(n log n) regardless of language.
How to solve Maximize Active Section with Trade II in O(n)?
Pure O(n) solutions are difficult because trade evaluation often requires testing multiple segment lengths or combinations. Most implementations use binary search with prefix arrays or a segment tree, giving O(n log n) complexity. The linear part comes from scanning the array or maintaining window feasibility checks.
What is the best approach for Maximize Active Section with Trade II?
The most practical solution uses Binary Search combined with prefix counts or a Segment Tree. Binary search guesses the maximum achievable active segment length, while prefix sums or range queries verify feasibility in O(n). This reduces the brute force search space and achieves about O(n log n) time complexity.
Is Maximize Active Section with Trade II asked at Google/Amazon/Meta?
Problems involving segment optimization, binary search on the answer, and segment tree aggregation frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of maximizing contiguous segments after operations are common in system design–style algorithm rounds.
What data structure is used in Maximize Active Section with Trade II?
Common structures include prefix sum arrays for fast range evaluation and Segment Trees for maintaining maximum contiguous segments under updates. The segment tree typically stores prefix active length, suffix active length, and the maximum active segment in each node.
What is the time complexity of Maximize Active Section with Trade II?
The optimal solutions typically run in O(n log n) time with O(n) space. Binary search over possible segment lengths adds the log n factor, while each feasibility check scans the array or performs segment tree queries. A naive brute force simulation can reach O(n^3) time and is impractical for large inputs.

Ready to solve this problem?

Practice Maximize Active Section with Trade II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays