2155. All Divisions With the Highest Score of a Binary Array LeetCode Solution

In this guide, you will get 2155. All Divisions With the Highest Score of a Binary Array LeetCode Solution with the best time and space complexity. The solution to All Divisions With the Highest Score of a Binary Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. All Divisions With the Highest Score of a Binary Array solution in C++
4. All Divisions With the Highest Score of a Binary Array solution in Java
5. All Divisions With the Highest Score of a Binary Array solution in Python
6. Additional Resources

Problem Statement of All Divisions With the Highest Score of a Binary Array

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) numsleft and numsright:

numsleft has all the elements of nums between index 0 and i – 1 (inclusive), while numsright has all the elements of nums between index i and n – 1 (inclusive).
If i == 0, numsleft is empty, while numsright has all the elements of nums.
If i == n, numsleft has all the elements of nums, while numsright is empty.

The division score of an index i is the sum of the number of 0's in numsleft and the number of 1's in numsright.
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: 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]
Explanation: 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]
Explanation: 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.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

2155. All Divisions With the Highest Score of a Binary Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> maxScoreIndices(vector<int>& nums) {
    const int zeros = ranges::count(nums, 0);
    const int ones = nums.size() - zeros;
    vector<int> ans{0};  // the division at index 0
    int leftZeros = 0;
    int leftOnes = 0;
    int maxScore = ones;  // `leftZeros` + `rightOnes`

    for (int i = 0; i < nums.size(); ++i) {
      leftZeros += nums[i] == 0;
      leftOnes += nums[i] == 1;
      const int rightOnes = ones - leftOnes;
      const int score = leftZeros + rightOnes;
      if (maxScore == score) {
        ans.push_back(i + 1);
      } else if (maxScore < score) {
        maxScore = score;
        ans = {i + 1};
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

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

class Solution {
  public List<Integer> maxScoreIndices(int[] nums) {
    final int ones = Arrays.stream(nums).sum();
    final int zeros = nums.length - ones;
    // the division at index 0
    List<Integer> 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;
  }
}
// code provided by PROGIEZ

2155. All Divisions With the Highest Score of a Binary Array LeetCode Solution in Python

class Solution:
  def maxScoreIndices(self, nums: list[int]) -> list[int]:
    zeros = nums.count(0)
    ones = len(nums) - zeros
    ans = [0]  # the division at index 0
    leftZeros = 0
    leftOnes = 0
    maxScore = ones  # `leftZeros` + `rightOnes`

    for i, num in enumerate(nums):
      leftZeros += num == 0
      leftOnes += num == 1
      rightOnes = ones - leftOnes
      score = leftZeros + rightOnes
      if maxScore == score:
        ans.append(i + 1)
      elif maxScore < score:
        maxScore = score
        ans = [i + 1]

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.