3897. Maximum Value of Concatenated Binary Segments

Hard

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integer arrays nums1 and nums0, each of size n.

nums1[i] represents the number of '1's in the i-th segment.
nums0[i] represents the number of '0's in the i-th segment.

For each index i, you build a binary segment that looks like this:

First, write nums1[i] copies of the character '1'.
Then, write nums0[i] copies of the character '0'.

So segment i is the string 1...1 (with nums1[i] ones) followed by 0...0 (with nums0[i] zeros).

You are allowed to rearrange these segments into any order you like. Once the order is fixed, you concatenate all the segments together to form one single binary string.

Your task is to choose the ordering that makes the resulting binary string represent the largest possible integer value. Because this value can be extremely large, return the answer modulo 10^9 + 7.

The intuition is that maximizing the integer value of a binary string is the same as making it as large as possible lexicographically, which means pushing as many '1's as far to the front (the high-order bits) as we can. The challenge is finding the right way to compare and order two segments so that the combined string is maximized.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Making the locally optimal choice at each step produces the globally optimal result.

Open in Flowchart

Intuition

The first thing to notice is that comparing two binary strings by their integer value is the same as comparing them by length first, and then lexicographically. But here, every possible arrangement uses all the segments, so the total length of the final string is always the same no matter how we order the segments. That means the length is fixed, and we only need to worry about making the string as large as possible lexicographically — getting '1's as close to the front as possible.

So the real question becomes: in what order should we place the segments?

Let's think about just two segments, A = 1^a 0^b and B = 1^c 0^d. We have only two choices: put them as AB or as BA. We should pick whichever concatenation gives the lexicographically larger string. By reasoning about this pairwise comparison, we can figure out a consistent sorting rule for all segments at once.

From comparing pairs, three natural cases emerge:

A segment with y = 0 is made of only '1's (no zeros at all). Placing it earlier never hurts, because it doesn't drag in any '0' to spoil the front. Among such pure-1 segments, the one with more '1's should go first, since more ones up front is strictly better.
A segment with x = 0 is made of only '0's. These can only lower the value when placed early, so we push them all the way to the end.
For a segment that has both ones and zeros (x > 0 and y > 0), we want the one with more leading '1's first, so we sort by x descending. When two segments have the same number of leading '1's, the next character that breaks the tie is a '0', so we'd rather "spend" fewer zeros early — sort by y ascending.

This gives a clean three-tier sorting key: pure-1 segments first (more ones first), then mixed segments (x descending, y ascending), then pure-0 segments last.

Once the order is decided, there's no need to actually build the giant binary string. We know the total length b of the concatenated string, so the leftmost character carries weight 2^(b-1), the next 2^(b-2), and so on. We precompute all powers of 2 modulo 10^9 + 7. Then we walk through the segments in sorted order from the highest bit downward: every time we hit a '1', we add the current bit's weight (2^position) to the answer; every time we hit a '0', we simply move the position pointer down without adding anything. This lets us compute the final value efficiently without ever materializing the full string.

Solution Approach

We use Sorting + Greedy to build the optimal order, then a power-of-two precomputation to compute the value efficiently.

Step 1: Pair up the segments.

We combine nums1 and nums0 into a list of pairs, where each pair (x, y) means the segment 1^x 0^y:

pairs = list(zip(nums1, nums0))

We also compute the total length b of the final concatenated string, since every arrangement uses all segments:

b = sum(x + y for x, y in pairs)

Step 2: Define the sorting key.

The greedy ordering from the intuition is encoded in a three-tier key. Python sorts tuples element by element, so we design the key so that the desired order falls out naturally in ascending sort:

def key(p):
    x, y = p
    if y == 0:
        return (0, -x, 0)   # pure '1' segments come first; more 1s first
    if x > 0:
        return (1, -x, y)   # mixed segments next; x descending, y ascending
    return (2, y, 0)        # pure '0' segments come last

The first element (0, 1, or 2) creates the three tiers: pure-1, mixed, pure-0.
For pure-1 segments, -x makes larger x sort earlier (more leading ones first).
For mixed segments, -x sorts x descending, and the third element y breaks ties by sorting y ascending (fewer zeros first).
Pure-0 segments all land in the last tier; their relative order doesn't affect the result.

Then we sort:

pairs.sort(key=key)

Step 3: Precompute powers of two.

Instead of constructing the huge binary string, we treat each '1' as contributing 2^position. We build an array p where p[i] = 2^i mod (10^9 + 7):

p = [1] * b
for i in range(1, b):
    p[i] = p[i - 1] * 2 % MOD

Step 4: Traverse and accumulate the answer.

We start at the highest bit position b - 1 (the leftmost character of the string). Walking through the sorted segments from front to back means walking from the highest bit downward:

b -= 1
for cnt1, cnt0 in pairs:
    while cnt1:
        ans = (ans + p[b]) % MOD   # a '1' adds the current bit's weight
        b -= 1
        cnt1 -= 1
    b -= cnt0                       # zeros only shift the position down

For each '1' in the current segment, we add p[b] (the weight 2^b) to the answer and move the position pointer down by one.
For the cnt0 zeros, we add nothing — we just decrement b by cnt0, since zeros do not contribute to the value but still occupy bit positions.

Step 5: Return the result.

After processing all segments, ans holds the maximum value modulo 10^9 + 7:

return ans

Complexity:

Time: O(n log n) for sorting plus O(m) for the precomputation and traversal, where n is the number of segments and m is the total length of the concatenated string.
Space: O(m) for the power-of-two array.

Example Walkthrough

Let's trace through a small example to see the solution approach in action.

Input:

nums1 = [2, 0, 1]
nums0 = [1, 2, 0]

Step 1: Pair up the segments and compute total length.

Pairing nums1 with nums0 gives us:

pairs = [(2, 1), (0, 2), (1, 0)]

Each pair (x, y) means the segment 1^x 0^y. Let's spell out each segment:

Index	Pair `(x, y)`	Segment string
0	`(2, 1)`	`"110"`
1	`(0, 2)`	`"00"`
2	`(1, 0)`	`"1"`

The total length is:

b = (2+1) + (0+2) + (1+0) = 3 + 2 + 1 = 6

So the final binary string will always have 6 bits, no matter the ordering.

Step 2: Apply the sorting key.

We compute the three-tier key for each pair:

Pair	Type	Key returned	Reasoning
`(2, 1)`	mixed	`(1, -2, 1)`	`x>0, y>0` → `(1, -x, y)`
`(0, 2)`	pure-`0`	`(2, 2, 0)`	`x==0` → `(2, y, 0)`
`(1, 0)`	pure-`1`	`(0, -1, 0)`	`y==0` → `(0, -x, 0)`

Sorting these keys in ascending order:

(0, -1, 0)  →  (1, 0)    [pure-1]
(1, -2, 1)  →  (2, 1)    [mixed]
(2,  2, 0)  →  (0, 2)    [pure-0]

So the sorted order is:

pairs = [(1, 0), (2, 1), (0, 2)]

Which corresponds to segments: "1" + "110" + "00" = "111000".

Sanity check — let's confirm this beats a naive alternative. The original order "110" + "00" + "1" = "110001". Comparing:

"111000" = 56
"110001" = 49

The sorted order wins, exactly as intended (push all the 1s to the front).

Step 3: Precompute powers of two.

With b = 6 and MOD = 10^9 + 7:

p = [1, 2, 4, 8, 16, 32]
   #  ^p[0] ... ^p[5]

Step 4: Traverse and accumulate.

We start at the highest bit position b = 5 and walk the sorted pairs from front to back. Below, ans starts at 0:

Segment	Action	Bit pos `b`	Weight `p[b]`	Running `ans`
`(1, 0)`	`'1'` → add `p[5]`	5 → 4	32	`0 + 32 = 32`
`(2, 1)`	`'1'` → add `p[4]`	4 → 3	16	`32 + 16 = 48`
`(2, 1)`	`'1'` → add `p[3]`	3 → 2	8	`48 + 8 = 56`
`(2, 1)`	`'0'` → shift only (`b -= 1`)	2 → 1	—	`56`
`(0, 2)`	two `'0'`s → shift only (`b -= 2`)	1 → -1	—	`56`

Each '1' adds the weight at its current bit position; each '0' just moves the pointer down without contributing.

Step 5: Return the result.

The final binary string "111000" equals:

1·2^5 + 1·2^4 + 1·2^3 + 0·2^2 + 0·2^1 + 0·2^0
= 32 + 16 + 8
= 56

This matches our accumulated ans = 56, so the answer is 56 (already less than 10^9 + 7, so no modulo reduction is needed here).

This walkthrough shows the key insight in motion: the length is fixed, so the greedy sort packs the 1s toward the high-order bits, and the power-of-two accumulation computes the value directly without ever materializing the full string.

Solution Implementation

1class Solution:
2    def maxValue(self, nums1: list[int], nums0: list[int]) -> int:
3        MOD = 10**9 + 7
4
5        # Pair up the count of ones (from nums1) and zeros (from nums0).
6        pairs = list(zip(nums1, nums0))
7
8        # Total number of bits in the final binary number.
9        total_bits = sum(ones + zeros for ones, zeros in pairs)
10
11        def sort_key(pair: tuple[int, int]) -> tuple[int, int, int]:
12            ones, zeros = pair
13            # Group 0: pure-ones pairs (no zeros). Place earliest so their
14            # 1-bits land in the highest positions; more ones first (-ones).
15            if zeros == 0:
16                return (0, -ones, 0)
17            # Group 1: mixed pairs with both ones and zeros.
18            # Prefer those with more ones first to push 1-bits higher.
19            if ones > 0:
20                return (1, -ones, zeros)
21            # Group 2: pure-zeros pairs (no ones). Fewer zeros first so we
22            # don't push remaining 1-bits down more than necessary.
23            return (2, zeros, 0)
24
25        pairs.sort(key=sort_key)
26
27        # Precompute powers of two: power[i] = 2^i mod MOD.
28        power = [1] * total_bits
29        for i in range(1, total_bits):
30            power[i] = power[i - 1] * 2 % MOD
31
32        ans = 0
33        # Current highest bit position available (0-indexed from the top).
34        position = total_bits - 1
35
36        for ones_count, zeros_count in pairs:
37            # Each '1' bit contributes 2^position to the value.
38            while ones_count:
39                ans = (ans + power[position]) % MOD
40                position -= 1
41                ones_count -= 1
42            # Each '0' bit just occupies a position, contributing nothing.
43            position -= zeros_count
44
45        return ans
46

1class Solution {
2    private static final int MOD = 1_000_000_007;
3
4    /**
5     * Greedily orders pairs of (ones, zeros) so that the '1' bits occupy the
6     * highest-value positions, then sums the corresponding powers of two.
7     *
8     * @param onesCounts number of '1' bits contributed by each element
9     * @param zerosCounts number of '0' bits contributed by each element
10     * @return the maximum value modulo 1e9+7
11     */
12    public int maxValue(int[] onesCounts, int[] zerosCounts) {
13        int n = onesCounts.length;
14
15        // pairs[i] = {ones, zeros} for element i
16        int[][] pairs = new int[n][2];
17
18        // totalBits accumulates every bit (ones + zeros) across all elements,
19        // which equals the total number of bit positions to fill.
20        int totalBits = 0;
21        for (int i = 0; i < n; ++i) {
22            pairs[i][0] = onesCounts[i];
23            pairs[i][1] = zerosCounts[i];
24            totalBits += onesCounts[i] + zerosCounts[i];
25        }
26
27        // Greedy ordering of blocks. Each block is classified into a group:
28        //   group 0: zeros == 0  -> pure-ones blocks, place first (they only add value)
29        //   group 1: zeros != 0 && ones > 0 -> mixed blocks
30        //   group 2: zeros != 0 && ones == 0 -> pure-zeros blocks, place last
31        Arrays.sort(pairs, (first, second) -> {
32            int ones1 = first[0], zeros1 = first[1];
33            int ones2 = second[0], zeros2 = second[1];
34
35            int group1 = zeros1 == 0 ? 0 : (ones1 > 0 ? 1 : 2);
36            int group2 = zeros2 == 0 ? 0 : (ones2 > 0 ? 1 : 2);
37
38            // Different groups: order by group index (0 before 1 before 2).
39            if (group1 != group2) {
40                return Integer.compare(group1, group2);
41            }
42
43            // group 0 (pure ones): more ones first to grab the highest positions.
44            if (group1 == 0) {
45                return Integer.compare(ones2, ones1);
46            }
47
48            // group 1 (mixed): prefer more ones first; tie-break by fewer zeros first.
49            if (group1 == 1) {
50                if (ones1 != ones2) {
51                    return Integer.compare(ones2, ones1);
52                }
53                return Integer.compare(zeros1, zeros2);
54            }
55
56            // group 2 (pure zeros): fewer zeros first.
57            return Integer.compare(zeros1, zeros2);
58        });
59
60        // Precompute powers of two modulo MOD: powerOfTwo[i] = 2^i % MOD.
61        long[] powerOfTwo = new long[totalBits];
62        powerOfTwo[0] = 1;
63        for (int i = 1; i < totalBits; ++i) {
64            powerOfTwo[i] = powerOfTwo[i - 1] * 2 % MOD;
65        }
66
67        long answer = 0;
68
69        // position tracks the current bit position (weight exponent), starting
70        // from the highest (totalBits - 1) and decreasing as we consume bits.
71        int position = totalBits - 1;
72
73        for (int[] pair : pairs) {
74            int remainingOnes = pair[0];
75            int remainingZeros = pair[1];
76
77            // Each '1' bit contributes 2^position to the answer.
78            while (remainingOnes-- > 0) {
79                answer = (answer + powerOfTwo[position--]) % MOD;
80            }
81
82            // '0' bits contribute nothing; just skip their positions.
83            position -= remainingZeros;
84        }
85
86        return (int) answer;
87    }
88}
89

1class Solution {
2public:
3    static constexpr int MOD = 1'000'000'007;
4
5    int maxValue(vector<int>& nums1, vector<int>& nums0) {
6        // Pair up the count of 1s (first) and count of 0s (second) for each index.
7        // Also accumulate the total number of bits.
8        vector<pair<int, int>> pairs;
9        int totalBits = 0;
10        for (int i = 0; i < static_cast<int>(nums1.size()); ++i) {
11            pairs.emplace_back(nums1[i], nums0[i]);
12            totalBits += nums1[i] + nums0[i];
13        }
14
15        // Sort the pairs so that, when laid out left-to-right (most significant
16        // bit first), the resulting binary string is maximized.
17        sort(pairs.begin(), pairs.end(), [](const auto& lhs, const auto& rhs) {
18            // Classify each pair into a priority group:
19            //   group 0: no zeros (pure ones)        -> place first
20            //   group 1: has zeros and at least one 1 -> place in the middle
21            //   group 2: has zeros and no ones        -> place last
22            auto group = [](const pair<int, int>& p) {
23                if (p.second == 0) {
24                    return 0;
25                }
26                if (p.first > 0) {
27                    return 1;
28                }
29                return 2;
30            };
31
32            int leftGroup = group(lhs);
33            int rightGroup = group(rhs);
34
35            // Different groups: order strictly by group priority.
36            if (leftGroup != rightGroup) {
37                return leftGroup < rightGroup;
38            }
39
40            // Group 0 (pure ones): more ones first to push bits leftward.
41            if (leftGroup == 0) {
42                return lhs.first > rhs.first;
43            }
44
45            // Group 1 (mixed): prefer more ones first; break ties by fewer zeros.
46            if (leftGroup == 1) {
47                if (lhs.first != rhs.first) {
48                    return lhs.first > rhs.first;
49                }
50                return lhs.second < rhs.second;
51            }
52
53            // Group 2 (pure zeros): fewer zeros first.
54            return lhs.second < rhs.second;
55        });
56
57        // Precompute powers of two modulo MOD.
58        // powerOfTwo[i] represents the weight of the bit at position i.
59        vector<long long> powerOfTwo(totalBits, 1);
60        for (int i = 1; i < totalBits; ++i) {
61            powerOfTwo[i] = powerOfTwo[i - 1] * 2 % MOD;
62        }
63
64        // Walk through the ordered pairs, assigning each bit a position weight.
65        // The most significant position is (totalBits - 1).
66        long long answer = 0;
67        int position = totalBits - 1;
68        for (auto& [countOnes, countZeros] : pairs) {
69            // Every '1' contributes 2^position to the final value.
70            while (countOnes-- > 0) {
71                answer = (answer + powerOfTwo[position--]) % MOD;
72            }
73            // Every '0' simply consumes a position without adding value.
74            position -= countZeros;
75        }
76
77        return static_cast<int>(answer);
78    }
79};
80

1const MOD = 1_000_000_007;
2
3/**
4 * Computes the maximum value by arranging bit groups to maximize the total sum.
5 * Each pair represents a count of 1-bits and 0-bits. The pairs are ordered so
6 * that the most significant bit positions are filled with 1s where it yields
7 * the greatest contribution, then the value is summed using powers of two.
8 *
9 * @param onesGroups - array where each element is the count of contiguous 1-bits in a group
10 * @param zerosGroups - array where each element is the count of contiguous 0-bits in a group
11 * @returns the maximum achievable value modulo 1e9+7
12 */
13function maxValue(onesGroups: number[], zerosGroups: number[]): number {
14    // Combine the two parallel arrays into pairs of [onesCount, zerosCount].
15    const pairs: [number, number][] = [];
16    // totalBits accumulates the total number of bit positions across all groups.
17    let totalBits = 0;
18
19    for (let i = 0; i < onesGroups.length; ++i) {
20        pairs.push([onesGroups[i], zerosGroups[i]]);
21        totalBits += onesGroups[i] + zerosGroups[i];
22    }
23
24    /**
25     * Classifies a pair into a group used for ordering:
26     *   group 0 -> the pair has no zeros (zeros === 0)
27     *   group 1 -> the pair has zeros and at least one 1-bit (ones > 0)
28     *   group 2 -> the pair has zeros but no 1-bits (ones === 0)
29     * The grouping determines the priority of placement at higher bit positions.
30     */
31    const classify = ([ones, zeros]: [number, number]): number => {
32        if (zeros === 0) {
33            return 0;
34        }
35        if (ones > 0) {
36            return 1;
37        }
38        return 2;
39    };
40
41    // Sort pairs to place the most valuable groups at the highest bit positions.
42    pairs.sort((first, second) => {
43        const groupFirst = classify(first);
44        const groupSecond = classify(second);
45
46        // Different groups: lower group index has higher priority.
47        if (groupFirst !== groupSecond) {
48            return groupFirst - groupSecond;
49        }
50
51        // Within group 0 (no zeros): prefer larger ones count first.
52        if (groupFirst === 0) {
53            return second[0] - first[0];
54        }
55
56        // Within group 1 (has zeros and ones): prefer larger ones count,
57        // and on ties, prefer fewer zeros.
58        if (groupFirst === 1) {
59            if (first[0] !== second[0]) {
60                return second[0] - first[0];
61            }
62            return first[1] - second[1];
63        }
64
65        // Within group 2 (no ones): prefer fewer zeros.
66        return first[1] - second[1];
67    });
68
69    // Precompute powers of two modulo MOD for each bit position.
70    const powerOfTwo = Array<number>(totalBits).fill(1);
71    for (let i = 1; i < totalBits; ++i) {
72        powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % MOD;
73    }
74
75    // Accumulate the answer by assigning the highest available bit positions
76    // to the 1-bits of each pair in the sorted order.
77    let answer = 0;
78    // currentBit points to the most significant remaining bit position.
79    let currentBit = totalBits - 1;
80
81    for (const [onesCount, zerosCount] of pairs) {
82        let remainingOnes = onesCount;
83
84        // Each 1-bit contributes 2^currentBit to the total value.
85        while (remainingOnes > 0) {
86            answer = (answer + powerOfTwo[currentBit]) % MOD;
87            --currentBit;
88            --remainingOnes;
89        }
90
91        // The zero bits occupy positions but contribute nothing to the value.
92        currentBit -= zerosCount;
93    }
94
95    return answer;
96}
97

Time and Space Complexity

The time complexity is O(n × log n + m), and the space complexity is O(n + m). Here, n is the number of segments (pairs), and m = Σ nums1[i] + Σ nums0[i].

Time Complexity: Building the pairs list via zip takes O(n). Sorting the pairs with the custom key function takes O(n × log n). Computing the prefix sum b requires O(n). Precomputing the power-of-two array p of length b = m takes O(m). The final nested loop over all pairs performs a total of Σ cnt1 increments to ans, bounded by m, so it costs O(m). Overall, the time complexity is O(n × log n + m).
Space Complexity: The pairs list uses O(n) space, and the precomputed power array p uses O(m) space. Thus, the total space complexity is O(n + m).

Common Pitfalls

Pitfall: Sorting mixed segments only by the number of ones, ignoring the zeros tie-breaker

The most subtle and common mistake is the comparison rule for mixed segments (those that contain both '1's and '0's). A natural-but-wrong instinct is to sort them purely by descending ones count, treating the zeros as irrelevant once the ones are ranked:

def sort_key(pair):
    ones, zeros = pair
    if zeros == 0:
        return (0, -ones, 0)
    if ones > 0:
        return (1, -ones)   # BUG: no tie-breaker on zeros
    return (2, zeros, 0)

Why this is wrong: When two mixed segments have the same number of leading ones, the placement of their zeros still affects every bit that follows. Consider two segments A = (1, 3) → "1000" and B = (1, 1) → "10". Both have one leading '1', so the wrong key treats them as equal and may keep them in arbitrary order.

A then B: "1000" + "10" = "100010"
B then A: "10" + "1000" = "101000"

The second ordering is larger, because placing the segment with fewer zeros first lets the next '1' rise to a higher bit position. The third tier zeros (ascending) in the correct key captures exactly this: among equal-ones segments, fewer zeros must come first.

Pitfall: Comparing segments by raw "value" or string concatenation like the "Largest Number" problem

A reflex carried over from the classic Largest Number (LeetCode 179) problem is to sort by comparing a + b vs b + a as concatenated strings. That comparator does not generalize here cleanly, and worse, building the strings is expensive and error-prone for large counts.

Solution: Trust the three-tier key — and verify it with a brute-force check on small inputs:

from itertools import permutations

def brute(nums1, nums0):
    MOD = 10**9 + 7
    pairs = list(zip(nums1, nums0))
    best = 0
    for perm in permutations(pairs):
        s = "".join("1" * x + "0" * y for x, y in perm)
        best = max(best, int(s, 2) % MOD)
    # NOTE: take int first, then mod, to avoid the next pitfall
    return best

# Compare brute() against the optimized solution on random small cases

Pitfall: Taking the modulo before choosing the maximum (in any verification)

If you ever fold a modulo into a comparison or a brute-force check, taking value % MOD before comparing destroys the ordering — a numerically larger string can produce a smaller residue. The greedy approach sidesteps this because it builds the string-order decision without modular arithmetic, applying % MOD only to the final accumulated bit-weights. Keep ordering decisions and modular reduction strictly separate.

Pitfall: Index-out-of-range when all segments are empty

If every pair is (0, 0), then total_bits = 0, and power = [1] * 0 = []. The loop body never touches power, so ans stays 0 — which is correct. But if you mistakenly initialize position = total_bits (instead of total_bits - 1) or access power[total_bits], you trigger an IndexError.

Solution: Anchor the position pointer at total_bits - 1 and let the loop decrement it; for the all-empty case the loop simply does nothing and returns 0 safely.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: