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

一刷 06/2022

Version #1 Count ones - 2 passes

Time O(N)

Space O(N)

Runtime: 47 ms, faster than 33.47% of Java online submissions for All Divisions With the Highest Score of a Binary Array.

Memory Usage: 192.7 MB, less than 25.21% of Java online submissions for All Divisions With the Highest Score of a Binary Array.

 class Solution {

    public List<Integer> maxScoreIndices(int[] nums) {

        // count of ones (including i) on the right of index i

        int[] rightOnes = new int[nums.length + 1];

        // rightZeros[nums.length] = 0

        int ones = 0;

        for (int i = nums.length - 1; i >= 0; i--) {

            if (nums[i] == 1) {

                ones++;

            }

            rightOnes[i] = ones;

        }

        int zeros = 0;

        int max = 0;

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i <= nums.length; i++) {

            if (i > 0 && nums[i - 1] == 0) {

                zeros++;

            }

            int score = zeros + rightOnes[i];

            // System.out.printf("index=%d, score=%d\n", i, score);

            if (score > max) {

                max = score;

                result.clear();

            }

            if (score == max) {

                result.add(i);

            }

        }

        return result;

    }

}