Maximum Value of Concatenated Binary Segments - Solution & Explanation

Problem Statement

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, construct a binary segment consisting of:

nums1[i] occurrences of '1' followed by
nums0[i] occurrences of '0'.

You may rearrange the order of these segments in any way. After rearranging, concatenate all segments to form a single binary string.

Return the maximum possible integer value of the concatenated binary string.

Since the result can be very large, return the answer modulo 10⁹ + 7.

Example 1:

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

Output: 14

Explanation:

At index 0, nums1[0] = 1 and nums0[0] = 1, so the segment formed is "10".
At index 1, nums1[1] = 2 and nums0[1] = 0, so the segment formed is "11".
Reordering the segments as "11" followed by "10" produces the binary string "1110".
The binary number "1110" has value 14 which is the maximum possible value.

Example 2:

Input: nums1 = [3,1], nums0 = [0,3]

Output: 120

Explanation:

At index 0, nums1[0] = 3 and nums0[0] = 0, so the segment formed is "111".
At index 1, nums1[1] = 1 and nums0[1] = 3, so the segment formed is "1000".
Reordering the segments as "111" followed by "1000" produces the binary string "1111000".
The binary number "1111000" has value 120 which is the maximum possible value.

Constraints:

1 <= n == nums1.length == nums0.length <= 10⁵
0 <= nums1[i], nums0[i] <= 10⁴
nums1[i] + nums0[i] > 0
The total sum of all elements in nums1 and nums0 does not exceed 2 * 10⁵.

Approach Overview

Problem Overview: You are given multiple binary segments and must concatenate them in some order to produce the largest possible binary value. The task is essentially choosing the best ordering of segments so the final concatenated binary string represents the maximum decimal value.

Approach 1: Brute Force Permutations (O(n! * k) time, O(n) space)

Generate every possible ordering of the binary segments using permutations. For each permutation, concatenate the segments and compute the resulting value (or compare the binary strings directly). Track the maximum result seen so far. This approach works for very small n but quickly becomes infeasible because the number of permutations grows factorially. It is mainly useful for understanding the problem and validating test cases.

Approach 2: Greedy Sorting by Concatenation Order (O(n log n * k) time, O(n) space)

The key insight: for two segments a and b, the better order is whichever produces a larger binary string between a + b and b + a. If a + b is larger, place a before b; otherwise place b first. Sorting all segments using this custom comparator produces the optimal global order. The comparison works because maximizing the most significant bits of the final concatenation dominates the value. Implement the comparator with string concatenation and lexicographic comparison. This pattern is similar to the classic “largest number by concatenation” problem and is naturally implemented with sorting and greedy reasoning.

Approach 3: Bit-Length Aware Comparison (O(n log n) comparisons, O(n) space)

Instead of building large intermediate strings repeatedly, treat each segment as a binary number with a known bit length. When comparing a before b versus b before a, compute the shifted values: (a << len(b)) | b and (b << len(a)) | a. Compare these two numbers to determine order. This reduces temporary string allocations and highlights the bit-level behavior of the concatenation. The technique relies on concepts from bit manipulation and works well when segment lengths are manageable.

Recommended for interviews: The greedy sorting comparator is what interviewers typically expect. Starting with the brute force permutation shows you understand the search space, but recognizing the a+b vs b+a ordering rule demonstrates the key greedy insight and reduces the complexity to O(n log n), which is scalable for large inputs.

Solution

Let the binary string corresponding to the i-th segment be 1^{x_i}0^{y_i}, where x_i = nums1[i] and y_i = nums0[i].

The problem allows us to rearrange these segments arbitrarily, and the goal is to maximize the integer value represented by the final concatenated binary string. Since comparing binary strings by value is essentially equivalent to comparing them lexicographically, we want as many 1s as possible to appear earlier.

Consider the relative order of two segments A = 1^a0^b and B = 1^c0^d. If we concatenate them as AB or BA, we should clearly choose the one with the larger lexicographical order.

Based on this rule, we can derive the following sorting strategy:

If a segment satisfies y = 0, it consists only of some 1s. Such segments should be placed as early as possible because they do not introduce any 0 prematurely. Among these segments, the one with more 1s should come first.
If two segments both satisfy x > 0 and y > 0, then the segment with more leading 1s should come first, so we sort by x in descending order. If x is the same, then the segment with fewer 0s should come first, so we sort by y in ascending order.
If a segment satisfies x = 0, it consists only of some 0s. Such segments should be placed at the end.

After sorting in this way, the concatenated binary string is maximized.

Next, we do not need to actually construct the whole binary string. Let the total length of all concatenated segments be m. We preprocess 2^0, 2^1, \dots, 2^{m-1} modulo 10^9 + 7. Then we traverse the segments in sorted order:

When we encounter a 1, we add the weight of the current highest bit to the answer.
When we encounter a 0, we only need to move the current position backward.

Finally, we obtain the answer.

The time complexity is O(n log n + m), and the space complexity is O(n + m). Here, n is the number of segments, and m = sum nums1[i] + sum nums0[i]. The problem guarantees that m \le 2 times 10^5.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Permutations	O(n! * k)	O(n)	Very small inputs or verifying correctness of other approaches
Greedy Sort by Concatenation (a+b vs b+a)	O(n log n * k)	O(n)	General case; standard optimal solution used in interviews
Bit-Length Aware Comparator	O(n log n)	O(n)	When avoiding large string concatenations and using numeric bit operations

Video Solution

LeetCode BiWeekly Contest 180 - Q4 - Maximum Value of Concatenated Binary Segments(3897) Explained • Kumar K [Amazon] • 715 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Maximum Value of Concatenated Binary Segments easy or hard?

This problem is typically categorized as Hard because it requires recognizing a non-obvious greedy ordering rule. While the final implementation is mostly sorting with a custom comparator, identifying the a+b vs b+a comparison insight is the challenging part.

Maximum Value of Concatenated Binary Segments Python/Java solution

Both Python and Java implementations follow the same strategy: define a comparator that compares a+b and b+a, sort the list of binary strings using that rule, then join the sorted segments into the final binary string. The complexity remains O(n log n) due to sorting.

How to solve Maximum Value of Concatenated Binary Segments in O(n)?

Pure O(n) is generally not achievable because the ordering must be determined by comparing segments. The practical optimal solution uses sorting with a custom comparator, resulting in O(n log n) time. The comparator evaluates a+b versus b+a to determine which segment should appear first.

What is the best approach for Maximum Value of Concatenated Binary Segments?

The best approach sorts binary segments using a custom comparator that checks which order produces a larger result: a+b or b+a. If a+b is larger, a should come before b. Sorting all segments with this rule forms the maximum possible concatenated binary value in O(n log n * k) time.

Is Maximum Value of Concatenated Binary Segments asked at Google/Amazon/Meta?

Problems based on concatenation ordering and greedy comparators appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of the classic 'largest number formed by concatenation' problem test understanding of greedy ordering and custom sorting logic.

What data structure is used in Maximum Value of Concatenated Binary Segments?

The solution mainly relies on arrays or lists to store the binary segments and a sorting algorithm with a custom comparator. Some optimized implementations also use bit manipulation by tracking each segment's bit length and comparing shifted values.

What is the time complexity of Maximum Value of Concatenated Binary Segments?

The optimal greedy solution runs in O(n log n * k) time where n is the number of segments and k is the average segment length. Sorting dominates the runtime, and each comparison checks the concatenations a+b and b+a. Space complexity is typically O(n) for storing the reordered segments.

Ready to solve this problem?

Practice Maximum Value of Concatenated Binary Segments with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance26.7%

Approaches1

Reading time16 min

Practice this problem

Open in Editor