LeetCode 2155. All Divisions With the Highest Score of a Binary Array Solution in Java, C++, Python & More | Explanation + Code

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) 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.

Solutions

Solution 1: Prefix Sum

We start from i = 0, using two variables l0 and r1 to respectively record the number of 1s to the left and right of i. Initially, l0 = 0, while r1 = ∑ nums.

We iterate through the array nums. For each i, we update l0 and r1, calculate the current grouping score t = l0 + r1. If t equals the current maximum grouping score mx, then we add i to the answer array. If t is greater than mx, we update mx to t, clear the answer array, and then add i to the answer array.

After the iteration ends, we return the answer array.

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

PythonJavaC++GoTypeScriptRust

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(code-box)

class Solution { public List<Integer> maxScoreIndices(int[] nums) { int l0 = 0, r1 = Arrays.stream(nums).sum(); int mx = r1; List<Integer> ans = new ArrayList<>(); ans.add(0); for (int i = 1; i <= nums.length; ++i) { int x = nums[i - 1]; l0 += x ^ 1; r1 -= x; int t = l0 + r1; if (mx == t) { ans.add(i); } else if (mx < t) { mx = t; ans.clear(); ans.add(i); } } return ans; } }(code-box)

class Solution { public: vector<int> maxScoreIndices(vector<int>& nums) { int l0 = 0, r1 = accumulate(nums.begin(), nums.end(), 0); int mx = r1; vector<int> ans = {0}; for (int i = 1; i <= nums.size(); ++i) { int x = nums[i - 1]; l0 += x ^ 1; r1 -= x; int t = l0 + r1; if (mx == t) { ans.push_back(i); } else if (mx < t) { mx = t; ans = {i}; } } return ans; } };(code-box)

func maxScoreIndices(nums []int) []int { l0, r1 := 0, 0 for _, x := range nums { r1 += x } mx := r1 ans := []int{0} for i, x := range nums { l0 += x ^ 1 r1 -= x t := l0 + r1 if mx == t { ans = append(ans, i+1) } else if mx < t { mx = t ans = []int{i + 1} } } return ans }(code-box)

function maxScoreIndices(nums: number[]): number[] { const n = nums.length; let [l0, r1] = [0, nums.reduce((a, b) => a + b, 0)]; let mx = r1; const ans: number[] = [0]; for (let i = 1; i <= n; ++i) { const x = nums[i - 1]; l0 += x ^ 1; r1 -= x; const t = l0 + r1; if (mx === t) { ans.push(i); } else if (mx < t) { mx = t; ans.length = 0; ans.push(i); } } return ans; }(code-box)

impl Solution { pub fn max_score_indices(nums: Vec<i32>) -> Vec<i32> { let mut l0 = 0; let mut r1: i32 = nums.iter().sum(); let mut mx = r1; let mut ans = vec![0]; for i in 1..=nums.len() { let x = nums[i - 1]; l0 += x ^ 1; r1 -= x; let t = l0 + r1; if mx == t { ans.push(i as i32); } else if mx < t { mx = t; ans = vec![i as i32]; } } ans } }(code-box)