Maximum Score After Binary Swaps - Solution & Explanation

Q: Is Maximum Score After Binary Swaps easy or hard?

Maximum Score After Binary Swaps is generally considered a Medium difficulty problem. The challenge comes from recognizing the greedy structure and efficiently selecting swaps using a heap rather than brute-force simulation.

Q: Maximum Score After Binary Swaps Python/Java solution

Implementations typically compute swap gains while iterating through the string, push them into a priority queue, and repeatedly extract the maximum gain. Python uses heapq (with negative values to simulate a max-heap), while Java uses PriorityQueue with a custom comparator. The same greedy logic applies across C++, Go, and TypeScript.

Q: How to solve Maximum Score After Binary Swaps in O(n log n)?

First scan the binary string and compute the score gain for every beneficial swap between a '0' and a '1'. Insert these gains into a max-heap. Repeatedly pop the largest gain, apply the swap logically, update any affected gains, and push them back into the heap. This greedy process ensures the highest contribution is always selected.

Q: What is the best approach for Maximum Score After Binary Swaps?

The most effective method uses a greedy strategy with a max-heap (priority queue). Compute the gain each potential swap would add to the score, push those gains into a max-heap, and repeatedly apply the swap with the highest benefit. This reduces the overall complexity to O(n log n) while always selecting the optimal next move.

Q: Is Maximum Score After Binary Swaps asked at Google/Amazon/Meta?

Problems combining greedy decisions with heap-based optimization frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving binary strings, swap optimization, and priority queues are common in coding interviews and online assessments.

Q: What data structure is used in Maximum Score After Binary Swaps?

The key data structure is a max-heap (priority queue). It efficiently tracks the swap that provides the highest score improvement at each step. Arrays or strings store the binary sequence, while the heap manages candidate gains.

Q: What is the time complexity of Maximum Score After Binary Swaps?

The optimal greedy solution runs in O(n log n) time because each candidate gain is inserted into or removed from a max-heap. Heap operations take O(log n), and up to O(n) swaps or updates may occur. Space complexity is O(n) to store gain values and heap entries.

MediumArray String Greedy Heap (Priority Queue)7 min readAsked at: Amazon

Practice this problem

Problem Statement

You are given an integer array nums of length n and a binary string s of the same length.

Initially, your score is 0. Each index i where s[i] = '1' contributes nums[i] to the score.

You may perform any number of operations (including zero). In one operation, you may choose an index i such that 0 <= i < n - 1, where s[i] = '0', and s[i + 1] = '1', and swap these two characters.

Return an integer denoting the maximum possible score you can achieve.

Example 1:

Input: nums = [2,1,5,2,3], s = "01010"

Output: 7

Explanation:

We can perform the following swaps:

Swap at index i = 0: "01010" changes to "10010"
Swap at index i = 2: "10010" changes to "10100"

Positions 0 and 2 contain '1', contributing nums[0] + nums[2] = 2 + 5 = 7. This is maximum score achievable.

Example 2:

Input: nums = [4,7,2,9], s = "0000"

Output: 0

Explanation:

There are no '1' characters in s, so no swaps can be performed. The score remains 0.

Constraints:

n == nums.length == s.length
1 <= n <= 10⁵
1 <= nums[i] <= 10⁹
s[i] is either '0' or '1'

Approach Overview

Problem Overview: You are given a binary string and can perform swaps between characters to increase a defined score. Each swap changes the arrangement of 0s and 1s, and the goal is to choose swaps that produce the maximum possible score after all operations.

Approach 1: Brute Force Simulation (O(n² log n) time, O(n) space)

The most direct strategy is to try all beneficial swaps between 0 and 1. For each candidate pair, simulate the swap and recompute the score impact based on how the relative ordering of bits changes. Because each swap evaluation may require scanning the string and recalculating contribution, the complexity grows quickly. This approach helps you understand how swaps affect the score but becomes impractical for large inputs.

Approach 2: Greedy with Max-Heap (Priority Queue) (O(n log n) time, O(n) space)

A better approach observes that every possible swap contributes a specific gain to the final score. Instead of recomputing the whole string repeatedly, compute the potential improvement each beneficial swap could produce. Store these gains in a max-heap so the most profitable swap is always chosen first. Each time you apply a swap, update any affected gains and push the new values back into the heap.

This greedy strategy works because the contribution of each swap can be evaluated independently and the best immediate improvement always moves the configuration closer to the optimal arrangement. Using a priority queue ensures efficient selection of the highest gain in O(log n) time. The approach processes the binary string once to compute initial gains and then repeatedly extracts the best candidate.

The implementation typically scans the string using array indexing while computing gain values derived from the relative positions of 0s and 1s. The greedy selection step is handled by a heap (priority queue). Conceptually, the method is a classic greedy optimization: always apply the swap that increases the score the most.

Recommended for interviews: Interviewers expect the greedy solution with a max-heap. Explaining the brute-force simulation first shows you understand how swaps affect the score. Transitioning to the heap-based greedy method demonstrates optimization skills and knowledge of priority queues, reducing the complexity to O(n log n) while keeping the logic clean and scalable.

Solution

According to the problem statement, each '1' can be swapped left any number of times, so each '1' can choose the largest unpicked number to its left. We can maintain these candidates with a max-heap.

Traverse the string s: for each position i, push the corresponding number nums[i] into the max-heap; if s[i] = '1', pop the maximum from the heap and add it to the answer.

After the traversal, the accumulated sum is the maximum score.

The time complexity is O(n log n) and the space complexity is O(n), where n is the length of the array nums.

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 Swap Simulation	O(n^2 log n)	O(n)	Useful for understanding how swaps affect score or when constraints are very small
Greedy with Max-Heap	O(n log n)	O(n)	General case solution; efficiently picks the highest-gain swap each step

Video Solution

Maximum Score After Binary Swaps | LeetCode 3781 | Biweekly Contest 172 • Sanyam IIT Guwahati • 565 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Score After Binary Swaps easy or hard?

Maximum Score After Binary Swaps is generally considered a Medium difficulty problem. The challenge comes from recognizing the greedy structure and efficiently selecting swaps using a heap rather than brute-force simulation.

Maximum Score After Binary Swaps Python/Java solution

Implementations typically compute swap gains while iterating through the string, push them into a priority queue, and repeatedly extract the maximum gain. Python uses heapq (with negative values to simulate a max-heap), while Java uses PriorityQueue with a custom comparator. The same greedy logic applies across C++, Go, and TypeScript.

How to solve Maximum Score After Binary Swaps in O(n log n)?

First scan the binary string and compute the score gain for every beneficial swap between a '0' and a '1'. Insert these gains into a max-heap. Repeatedly pop the largest gain, apply the swap logically, update any affected gains, and push them back into the heap. This greedy process ensures the highest contribution is always selected.

What is the best approach for Maximum Score After Binary Swaps?

The most effective method uses a greedy strategy with a max-heap (priority queue). Compute the gain each potential swap would add to the score, push those gains into a max-heap, and repeatedly apply the swap with the highest benefit. This reduces the overall complexity to O(n log n) while always selecting the optimal next move.

Is Maximum Score After Binary Swaps asked at Google/Amazon/Meta?

Problems combining greedy decisions with heap-based optimization frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving binary strings, swap optimization, and priority queues are common in coding interviews and online assessments.

What data structure is used in Maximum Score After Binary Swaps?

The key data structure is a max-heap (priority queue). It efficiently tracks the swap that provides the highest score improvement at each step. Arrays or strings store the binary sequence, while the heap manages candidate gains.

What is the time complexity of Maximum Score After Binary Swaps?

The optimal greedy solution runs in O(n log n) time because each candidate gain is inserted into or removed from a max-heap. Heap operations take O(log n), and up to O(n) swaps or updates may occur. Space complexity is O(n) to store gain values and heap entries.

Ready to solve this problem?

Practice Maximum Score After Binary Swaps with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance35.0%

Approaches1

Reading time7 min

Asked at

Amazon