MediumNo. 2155
All Divisions With the Highest Score of a Binary Array — LeetCode 2155 Python Solution
- Topics
- Array
- 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
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 ansComplexity
- Time
- O(n)where n is the length of the array nums
- Space · auxiliary
- O(1)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
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.