#2155

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

All Divisions With the Highest Score of a Binary Array

Find all indices in a binary array where division score is maximized.

Problem Statement

You are given a binary array nums of length n. Your task is to find all possible indices i such that the array can be split into two subarrays numsleft and numsright at that index i, where numsleft consists of elements before index i and numsright consists of elements from index i onward.

The division score at index i is defined as the sum of the number of 0's in numsleft and the number of 1's in numsright. You need to return all distinct indices where the division score is maximized. Indices can be returned in any order.

Examples

Example 1

Input: nums = [0,0,1,0]

Output: [2,4]

Division at index

0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3. Indices 2 and 4 both have the highest possible division score 3. Note the answer [4,2] would also be accepted.

Example 2

Input: nums = [0,0,0]

Output: [3]

Division at index

0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3. Only index 3 has the highest possible division score 3.

Example 3

Input: nums = [1,1]

Output: [0]

Division at index

0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0. Only index 0 has the highest possible division score 2.

Constraints

n == nums.length
1 <= n <= 105
nums[i] is either 0 or 1.

Solution Approach

Iterate with Counting

Start by maintaining running counts of 0's in the left subarray and 1's in the right subarray as you iterate through the array. For each division index, compute the division score by summing the number of 0's to the left and the number of 1's to the right.

Precompute Right Counts

Precompute the number of 1's in the right subarray for each index. This avoids recomputing the count of 1's for each division point, improving efficiency.

Optimized Complexity

By using precomputed counts and iterating through the array once, the solution can run in linear time, O(n), making it efficient even for large arrays with up to 100,000 elements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we iterate over the array once to compute division scores. Space complexity is O(n) due to storing the precomputed right counts.

What Interviewers Usually Probe

Candidate should maintain running counts of 0's and 1's.
Look for clear explanation of optimizing through precomputation.
Expect understanding of array-driven solutions and space-time trade-offs.

Common Pitfalls or Variants

Common pitfalls

Not maintaining running counts of 0's and 1's efficiently.
Incorrect handling of boundary conditions for division (e.g., empty left or right subarrays).
Failing to optimize by precomputing the right side counts.

Follow-up variants

Consider cases with very small arrays, including edge cases with 1 or 2 elements.
Test with large arrays near the maximum constraint to ensure performance.
Explore different ways of maintaining the counts (e.g., using two passes instead of one).

FAQ

How do I optimize the solution for large arrays?

Precomputing the right counts of 1's for each index and maintaining a running count of 0's on the left allows you to solve the problem in linear time, O(n).

What is the division score?

The division score is the sum of the number of 0's in the left subarray and the number of 1's in the right subarray.

What is the pattern for solving this problem?

The problem follows an array-driven solution strategy where you calculate division scores using running counts and precomputed data to ensure efficiency.

How do I handle edge cases in this problem?

Handle cases like empty left or right subarrays carefully, and ensure that indices at the boundaries are processed correctly.

Can this problem be solved in less than O(n) time?

No, the optimal solution requires at least one pass through the array to calculate the division scores, making O(n) the best achievable time complexity.

terminal

Solution

Solution 1: Prefix Sum

We start from $i = 0$, using two variables $\textit{l0}$ and $\textit{r1}$ to respectively record the number of $1$s to the left and right of $i$. Initially, $\textit{l0} = 0$, while $\textit{r1} = \sum \textit{nums}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        l0, r1 = 0, sum(nums)
        mx = r1
        ans = [0]
        for i, x in enumerate(nums, 1):
            l0 += x ^ 1
            r1 -= x
            t = l0 + r1
            if mx == t:
                ans.append(i)
            elif mx < t:
                mx = t
                ans = [i]
        return ans

Continue Practicing

#2154 keep multiplying found values by two #2151 maximum good people based on statements #2150 find all lonely numbers in the array