Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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).i == 0, numsleft is empty, while numsright has all the elements of nums.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.length1 <= n <= 105nums[i] is either 0 or 1.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[0,0,1,0]
[0,0,0]
[1,1]
ones-and-zeroes)max-consecutive-ones-ii)count-subarrays-with-more-ones-than-zeros)array-partition)divide-array-in-sets-of-k-consecutive-numbers)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2155: All Divisions With the Highest Score of a Binary Array
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;
}
}
// Accepted solution for LeetCode #2155: All Divisions With the Highest Score of a Binary Array
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
}
# Accepted solution for LeetCode #2155: All Divisions With the Highest Score of a Binary Array
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
// Accepted solution for LeetCode #2155: All Divisions With the Highest Score of a Binary Array
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
}
}
// Accepted solution for LeetCode #2155: All Divisions With the Highest Score of a Binary Array
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.