[LeetCode] All Divisions With the Highest Score of a Binary Array

Problem: 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:

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.

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.

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.

Approach: The problem is simple, we iterate through the the array we need to maintain number of 0s at the left and number of 1s on the right. Now how we can quickly calculate it?

The number of 1s on the right will be the sum of array minus the number of 1s on the left. To calculate the number of 1s quickly we can maintain prefix array sum. Now you can see the calculation:

• Number of 0s on the left at index i = i  - prefixSum[i - 1] 
• prefixSum[i - 1] will tell the number of 1s at the left
• If we subtract the prefixSum[i - 1] from i, it will tell the number of 0s on the left
• Number of 1s on the right at index i = SUM(nums) - prefixSum[i - 1]

Now we just need to calculate the maximum of the sum of above two values at each index i and return all the i's which has the maximum sum.

Implementation in C#:

    public IList<int> MaxScoreIndices(int[] nums)

    {

        IList<int> result = new List<int>();

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return result;

        }

        int arrSum = nums[0];

        for (int i = 1; i < length; ++i)

        {

            arrSum += nums[i];

            nums[i] += nums[i - 1];

        }

        int maxScore = arrSum;

        result.Add(0);

        for (int i = 1; i < length; ++i)

        {

            int currScore = i - nums[i - 1];

            currScore += (arrSum - nums[i - 1]);

            if (currScore > maxScore)

            {

                maxScore = currScore;

                result = new List<int>();

                result.Add(i);

            }

            else if (currScore == maxScore)

            {

                result.Add(i);

            }

        }

        int lastScore = length - arrSum;

        if (lastScore > maxScore)

        {

            maxScore = lastScore;

            result = new List<int>();

            result.Add(length);

        }

        else if (lastScore == maxScore)

        {

            result.Add(length);

        }

        return result;

    }

Complexity: O(n)