3501. Maximize Active Section with Trade II

  • String
  • Binary Search
  • Sparse Table
  • Prefix Sum
  • Greedy
TIME
O(n log n + q log n)
SPACE
O(n log n)
problem on leetcode ↗source on github ↗

Intuition

Part I established the core accounting: on t = '1' + substring + '1', a trade around a 1-run B flanked by 0-runs A and C nets exactly A + C (you lose B, then regain it inside the merged block). So per query:

answer = total_ones(s) + bestGain(l, r)

total_ones(s) is a constant, the characters outside [l, r] are untouched, and the ones inside are fully accounted for by the gain. What changes per query is bestGain(l, r) = the largest sum of two adjacent zero-runs inside the augmented substring.

The only subtlety versus part I is clipping: the first and last zero-runs touching [l, r] are cut off at the query boundary, while every run strictly inside keeps its full length.

Approach

Preprocessing:

  1. Collect all maximal zero-runs of s as (start, end) with full lengths.
  2. Build P[i] = len[i] + len[i+1] the adjacent-pair sums, which never depend on a query.
  3. Build a sparse table over P for O(1) range-maximum queries.

Per query [l, r]:

  1. Binary-search the range of runs intersecting [l, r]: a = first run with end >= l, b = last run with start <= r. If a > b, no zero-runs → gain 0.
  2. If a == b, only one zero-run exists → no adjacent pair → gain 0.
  3. Compute the clipped boundary lengths:
    • lenA = min(end_a, r) - max(start_a, l) + 1
    • lenB = min(end_b, r) - max(start_b, l) + 1
  4. Take the max of:
    • the leading pair (a, a+1): lenA + (a+1 == b ? lenB : fullLen[a+1])
    • the trailing pair (b-1, b): (b-1 == a ? lenA : fullLen[b-1]) + lenB
    • the interior pairs: sparse-table range max of P over [a+1, b-2] (only when a+1 <= b-2)
  5. answer = total_ones + gain.

Complexity

  • Time: O(n log n) preprocessing + O(log n) per query for the binary searches (range max is O(1))
  • Space: O(n log n), the sparse table

Edge Cases

  • Query range with no zeros, or only one zero-run → gain 0 (no valid trade)
  • a == b must return 0, not 2 * lenA a single run has no adjacent partner
  • b == a + 1 → exactly one pair, both lengths clipped
  • Boundary runs partially outside [l, r] → must use clipped, not full, lengths
  • Answer counts ones across all of s, not just the substring (untouched characters still count)

Code

from typing import List
from bisect import bisect_left, bisect_right


class Solution:
    def maxActiveSectionsAfterTrade(self, s: str, queries: List[List[int]]) -> List[int]:
        """
        3501. Maximize Active Section with Trade II
        Time: O(n log n + q log n)
        Space: O(n log n)
        """
        n = len(s)
        total_ones = s.count("1")

        # Maximal zero-runs of s.
        starts, ends, lengths = [], [], []
        i = 0
        while i < n:
            if s[i] == "0":
                j = i
                while j < n and s[j] == "0":
                    j += 1
                starts.append(i)
                ends.append(j - 1)
                lengths.append(j - i)
                i = j
            else:
                i += 1

        cnt = len(starts)

        # P[i] = full adjacent-pair sum; sparse table for range max.
        P = [lengths[i] + lengths[i + 1] for i in range(cnt - 1)]
        m = len(P)
        LOG = max(1, m.bit_length())
        sparse = [P[:]] if m else [[]]
        k = 1
        while (1 << k) <= m:
            prev = sparse[k - 1]
            span = 1 << (k - 1)
            sparse.append([max(prev[i], prev[i + span]) for i in range(m - (1 << k) + 1)])
            k += 1

        def range_max(lo: int, hi: int) -> int:
            # max of P[lo..hi]; caller guarantees lo <= hi and valid bounds
            k = (hi - lo + 1).bit_length() - 1
            return max(sparse[k][lo], sparse[k][hi - (1 << k) + 1])

        ans = []
        for l, r in queries:
            a = bisect_left(ends, l)          # first run with end >= l
            b = bisect_right(starts, r) - 1   # last run with start <= r

            if a > b or a >= cnt or b < 0:
                ans.append(total_ones)
                continue
            if a == b:
                # single zero-run: no adjacent partner, no valid trade
                ans.append(total_ones)
                continue

            len_a = min(ends[a], r) - max(starts[a], l) + 1
            len_b = min(ends[b], r) - max(starts[b], l) + 1

            # leading pair (a, a+1) and trailing pair (b-1, b)
            gain = len_a + (len_b if a + 1 == b else lengths[a + 1])
            gain = max(gain, (len_a if b - 1 == a else lengths[b - 1]) + len_b)

            # fully-interior pairs
            if a + 1 <= b - 2:
                gain = max(gain, range_max(a + 1, b - 2))

            ans.append(total_ones + gain)
        return ans