All Divisions With the Highest Score of a Binary Array

MEDIUM

Description

You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) nums_left and nums_right:

nums_left has all the elements of nums between index 0 and i - 1 (inclusive), while nums_right has all the elements of nums between index i and n - 1 (inclusive).
If i == 0, nums_left is empty, while nums_right has all the elements of nums.
If i == n, nums_left has all the elements of nums, while nums_right is empty.

The division score of an index i is the sum of the number of 0's in nums_left and the number of 1's in nums_right.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example 1:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: nums_left is [0]. nums_right is [0,1,0]. The score is 1 + 1 = 2.
- 2: nums_left is [0,0]. nums_right is [1,0]. The score is 2 + 1 = 3.
- 3: nums_left is [0,0,1]. nums_right is [0]. The score is 2 + 0 = 2.
- 4: nums_left is [0,0,1,0]. nums_right 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]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,0]. The score is 0 + 0 = 0.
- 1: nums_left is [0]. nums_right is [0,0]. The score is 1 + 0 = 1.
- 2: nums_left is [0,0]. nums_right is [0]. The score is 2 + 0 = 2.
- 3: nums_left is [0,0,0]. nums_right 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]
Explanation: Division at index
- 0: nums_left is []. nums_right is [1,1]. The score is 0 + 2 = 2.
- 1: nums_left is [1]. nums_right is [1]. The score is 0 + 1 = 1.
- 2: nums_left is [1,1]. nums_right is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Constraints:

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

Approaches

Checkout 3 different approaches to solve All Divisions With the Highest Score of a Binary Array. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach directly simulates the process described in the problem. It iterates through every possible division index i from 0 to n. For each index, it calculates the score by explicitly counting the number of zeros in the left part (nums_left) and the number of ones in the right part (nums_right). It keeps track of the maximum score seen so far and the list of indices that achieve this score.

Algorithm

Initialize maxScore to -1 and result as an empty list.
Loop through each possible division index i from 0 to n.
- Calculate zerosLeft by iterating from index 0 to i-1.
- Calculate onesRight by iterating from index i to n-1.
- Compute currentScore = zerosLeft + onesRight.
- If currentScore > maxScore, update maxScore to currentScore and reset result to contain only i.
- If currentScore == maxScore, add i to result.
Return result.

We iterate through all possible division points i from 0 to n. For each i, we perform two separate counts:

Iterate from the beginning of the array up to i-1 to count the zeros (zerosLeft).
Iterate from index i to the end of the array to count the ones (onesRight). The score for index i is zerosLeft + onesRight. We maintain a variable maxScore and a list resultIndices. If the current score is greater than maxScore, we update maxScore and replace resultIndices with a new list containing just i. If the current score is equal to maxScore, we simply add i to resultIndices. This process is repeated for all n+1 possible division points. The main drawback is the repeated counting. For each division point, we traverse significant portions of the array, leading to a quadratic time complexity.

public List<Integer> maxScoreIndices(int[] nums) {
    int n = nums.length;
    List<Integer> result = new ArrayList<>();
    int maxScore = -1;

    for (int i = 0; i <= n; i++) {
        int zerosLeft = 0;
        for (int j = 0; j < i; j++) {
            if (nums[j] == 0) {
                zerosLeft++;
            }
        }

        int onesRight = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 1) {
                onesRight++;
            }
        }

        int currentScore = zerosLeft + onesRight;

        if (currentScore > maxScore) {
            maxScore = currentScore;
            result.clear();
            result.add(i);
        } else if (currentScore == maxScore) {
            result.add(i);
        }
    }
    return result;
}

Complexity Analysis

Time Complexity: O(n^2). For each of the `n+1` division points, we iterate over the array, which takes `O(n)` time.Space Complexity: O(1) auxiliary space. The space for the result list is not counted as auxiliary space.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the problem definition.

Cons:

Highly inefficient due to redundant calculations.
Time complexity is quadratic, which is too slow for large inputs (n up to 10^5).

Code Solutions

Checking out 3 solutions in different languages for All Divisions With the Highest Score of a Binary Array. Click on different languages to view the code.

class Solution {
public
  List<Integer> maxScoreIndices(int[] nums) {
    int left = 0, right = sum(nums);
    int mx = right;
    List<Integer> ans = new ArrayList<>();
    ans.add(0);
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == 0) {
        ++left;
      } else {
        --right;
      }
      int t = left + right;
      if (mx == t) {
        ans.add(i + 1);
      } else if (mx < t) {
        mx = t;
        ans.clear();
        ans.add(i + 1);
      }
    }
    return ans;
  }
private
  int sum(int[] nums) {
    int s = 0;
    for (int num : nums) {
      s += num;
    }
    return s;
  }
}

Video Solution

Watch the video walkthrough for All Divisions With the Highest Score of a Binary Array

Data Structures:

Array