How hard is LeetCode 2155. All Divisions With the Highest Score of a Binary Array?

LeetCode 2155. All Divisions With the Highest Score of a Binary Array is rated Medium on LeetCode.

What is the time complexity of LeetCode 2155. All Divisions With the Highest Score of a Binary Array?

The Python solution on this page runs in O(n), where n is the length of the array \textit{nums}.

What is the space complexity of LeetCode 2155. All Divisions With the Highest Score of a Binary Array?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2155. All Divisions With the Highest Score of a Binary Array cover?

LeetCode 2155. All Divisions With the Highest Score of a Binary Array is tagged Array on LeetCode.

All Divisions With the Highest Score of a Binary Array — LeetCode 2155 Python Solution

MediumArray

Problem: #2155
Reading time: 3 min
Source: leetcode.com

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

Example

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array \textit{nums}
Space	O(1) auxiliary

Frequently asked questions

How hard is LeetCode 2155. All Divisions With the Highest Score of a Binary Array?: LeetCode 2155. All Divisions With the Highest Score of a Binary Array is rated Medium on LeetCode.
What is the time complexity of LeetCode 2155. All Divisions With the Highest Score of a Binary Array?: The Python solution on this page runs in O(n), where n is the length of the array \textit{nums}.
What is the space complexity of LeetCode 2155. All Divisions With the Highest Score of a Binary Array?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2155. All Divisions With the Highest Score of a Binary Array cover?: LeetCode 2155. All Divisions With the Highest Score of a Binary Array is tagged Array on LeetCode.