All Divisions With the Highest Score of a Binary Array Solution in Java

Explore Solutions in Other Languages

Problem Description

Ah, the classic dilemma of dividing a binary array into two parts and trying to score points like it’s a game of Monopoly! The problem is simple yet perplexing: given an array of 0s and 1s, you need to find all the indices where you can “cut” the array into two parts such that the score is maximized. The score is calculated as the number of 0s on the left side plus the number of 1s on the right side.

Imagine you’re at a party, and you have to decide where to cut the cake (the binary array). You want to make sure that the left side has the most frosting (0s) while the right side has the most delicious fruit (1s). But, of course, you can’t just cut anywhere; you have to find the perfect spot!

Code Solution


class Solution {
  public List maxScoreIndices(int[] nums) {
    final int ones = Arrays.stream(nums).sum();
    final int zeros = nums.length - ones;
    // the division at index 0
    List ans = new ArrayList<>(List.of(0));
    int leftZeros = 0;
    int leftOnes = 0;
    int maxScore = ones; // `leftZeros` + `rightOnes`

    for (int i = 0; i < nums.length; ++i) {
      leftZeros += nums[i] == 0 ? 1 : 0;
      leftOnes += nums[i] == 1 ? 1 : 0;
      final int rightOnes = ones - leftOnes;
      final int score = leftZeros + rightOnes;
      if (maxScore == score) {
        ans.add(i + 1);
      } else if (maxScore < score) {
        maxScore = score;
        ans = new ArrayList<>(List.of(i + 1));
      }
    }

    return ans;
  }
}

Approach Explanation

The approach is straightforward yet elegant. The code first calculates the total number of 1s in the array. Then, it iterates through the array while keeping track of the number of 0s on the left and the number of 1s on the right. For each index, it calculates the score and updates the maximum score and the list of indices accordingly. It’s like a game of keeping score while trying to balance the cake!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the input array. We traverse the array only once.
Space Complexity	O(k), where k is the number of indices with the maximum score. This is because we store the indices in a list.

Real-World Example

Let’s say you’re organizing a talent show. You have a list of participants where 0 represents a singer and 1 represents a dancer. You want to split the participants into two groups: one for singers and one for dancers. The goal is to maximize the number of singers in the first group and dancers in the second group. This problem is just like that!