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

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

Python3JavaC++GoTypeScript

class Solution:
    def maxScoreIndices(self, nums: List[int]) -> List[int]:
        left, right = 0, sum(nums)
        mx = right
        ans = [0]
        for i, num in enumerate(nums):
            if num == 0:
                left += 1
            else:
                right -= 1
            t = left + right
            if mx == t:
                ans.append(i + 1)
            elif mx < t:
                mx = t
                ans = [i + 1]
        return ans

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;
    }
}

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

func maxScoreIndices(nums []int) []int {
    left, right := 0, 0
    for _, num := range nums {
        right += num
    }
    mx := right
    ans := []int{0}
    for i, num := range nums {
        if num == 0 {
            left++
        } else {
            right--
        }
        t := left + right
        if mx == t {
            ans = append(ans, i+1)
        } else if mx < t {
            mx = t
            ans = []int{i + 1}
        }
    }
    return ans
}

function maxScoreIndices(nums: number[]): number[] {
    const n = nums.length;
    const total = nums.reduce((a, c) => a + c, 0);
    let left = 0,
        right = total;
    let record: Array<number> = [total];
    for (const num of nums) {
        if (num == 0) {
            left++;
        } else {
            right--;
        }
        record.push(left + right);
    }
    const max = Math.max(...record);
    let ans: Array<number> = [];
    for (let i = 0; i <= n; i++) {
        if (record[i] == max) {
            ans.push(i);
        }
    }
    return ans;
}

Comments