Maximize Active Section with Trade II - Practice Coding Problems

Maximize Active Section with Trade II - Problem

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] = [l_i, r_i] represents a substring s[l_i...r_i].

For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[l_i...r_i].

Return an array answer, where answer[i] is the result for queries[i].

Note: For each query, treat s[l_i...r_i] as if it is augmented with a '1' at both ends, forming t = '1' + s[l_i...r_i] + '1'. The augmented '1's do not contribute to the final count. The queries are independent of each other.

Input & Output

Example 1 — Basic Trade

$ Input: s = "10110", queries = [[1,3]]

› Output: [3]

💡 Note: Query [1,3] gives substring "011". Augmented: "1011". We can trade the '1' block (position 0) with '00' block (positions 1-2) to get "100" → 3 ones total in original string.

Example 2 — Multiple Queries

$ Input: s = "1100", queries = [[0,1],[2,3]]

› Output: [2,2]

💡 Note: Query [0,1]: "11" → augmented "111", no beneficial trade. Query [2,3]: "00" → augmented "100", can convert to "111" for 2 total ones.

Example 3 — No Trade Needed

$ Input: s = "111", queries = [[0,2]]

› Output: [3]

💡 Note: All positions are already '1', no trade can improve the count.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'
1 ≤ queries.length ≤ 10⁵
0 ≤ l_i ≤ r_i < s.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s and query ranges

Process

For each query, augment substring and find optimal trade

Output

Array of maximum active sections for each query

Key Takeaway

🎯 Key Insight: The optimal trade always involves swapping blocks to maximize the net gain of '1's in the query range

Asked in

G Google 35 f Meta 28 a Amazon 22 M Microsoft 18

This problem requires analyzing binary string trades within query ranges. The key insight is that we need to find the optimal swap between a '1' block and a '0' block after augmenting the substring. The optimized approach uses prefix sums for O(1) counting and efficient block identification. Time: O(Q × N), Space: O(N).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Preprocessing	O(N log N + Q log N)	O(N)	Preprocess blocks and use efficient data structures to avoid redundant calculations
Brute Force - Try All Possible Trades	O(Q × N³)	O(N)	For each query, try all possible combinations of '1' blocks to turn off and '0' blocks to turn on

Optimized with Preprocessing — Algorithm Steps

Build a segment tree or similar structure to handle range queries efficiently
Preprocess all possible contiguous blocks in the string
For each query, use preprocessed data to quickly find optimal trade
Calculate result using prefix sums and cached block information

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Build prefix sums for O(1) counting

Smart Blocks

Find blocks efficiently with augmentation

Quick Trade

Use precomputed data for fast swaps

O(log N) Query

Each query processes in logarithmic time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(char* s, int queries[][2], int queryCount, int* returnSize) {
    int n = strlen(s);
    int* result = (int*)malloc(queryCount * sizeof(int));
    *returnSize = queryCount;
    
    // Precompute prefix sums
    int* prefixOnes = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < n; i++) {
        prefixOnes[i + 1] = prefixOnes[i] + (s[i] == '1' ? 1 : 0);
    }
    
    for (int q = 0; q < queryCount; q++) {
        int l = queries[q][0], r = queries[q][1];
        int substrLen = r - l + 1;
        char* substr = (char*)malloc((substrLen + 1) * sizeof(char));
        strncpy(substr, s + l, substrLen);
        substr[substrLen] = '\0';
        
        char* augmented = (char*)malloc((substrLen + 3) * sizeof(char));
        sprintf(augmented, "1%s1", substr);
        
        int originalOnes = prefixOnes[r + 1] - prefixOnes[l];
        int maxOnes = originalOnes;
        
        // Find blocks and try combinations
        int augLen = strlen(augmented);
        for (int i = 1; i < augLen - 1; ) {
            if (augmented[i] == '1') {
                int oneStart = i;
                while (i < augLen - 1 && augmented[i] == '1') i++;
                int oneEnd = i - 1;
                
                for (int j = 1; j < augLen - 1; ) {
                    if (augmented[j] == '0') {
                        int zeroStart = j;
                        while (j < augLen - 1 && augmented[j] == '0') j++;
                        int zeroEnd = j - 1;
                        
                        int onesLost = oneEnd - oneStart + 1;
                        int onesGained = zeroEnd - zeroStart + 1;
                        int newCount = originalOnes - onesLost + onesGained;
                        if (newCount > maxOnes) {
                            maxOnes = newCount;
                        }
                    } else {
                        j++;
                    }
                }
            } else {
                i++;
            }
        }
        
        result[q] = maxOnes;
        free(substr);
        free(augmented);
    }
    
    free(prefixOnes);
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char queryLine[100001];
    fgets(queryLine, sizeof(queryLine), stdin);
    queryLine[strcspn(queryLine, "\n")] = 0;
    
    int queries[1000][2];
    int queryCount = 0;
    
    char* token = strtok(queryLine + 1, "],[");
    while (token != NULL) {
        sscanf(token, "%d,%d", &queries[queryCount][0], &queries[queryCount][1]);
        queryCount++;
        token = strtok(NULL, "],[");
    }
    
    int returnSize;
    int* result = solution(s, queries, queryCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N log N + Q log N)

Preprocessing takes O(N log N), each query takes O(log N)

⚡ Linearithmic

Space Complexity

O(N)

Store segment tree and preprocessed block information

✓ Linear Space

23.2K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler