Package g2101_2200.s2155_all_divisions_with_the_highest_score_of_a_binary_array

Class Solution

java.lang.Object

g2101_2200.s2155_all_divisions_with_the_highest_score_of_a_binary_array.Solution

public class Solution
extends Object

2155 - All Divisions With the Highest Score of a Binary Array.<p>Medium</p> <p>You are given a <strong>0-indexed</strong> binary array <code>nums</code> of length <code>n</code>. <code>nums</code> can be divided at index <code>i</code> (where <code>0 <= i <= n)</code> into two arrays (possibly empty) <code>nums_left</code> and <code>nums_right</code>:</p> <ul> <li><code>nums_left</code> has all the elements of <code>nums</code> between index <code>0</code> and <code>i - 1</code> <strong>(inclusive)</strong> , while <code>nums_right</code> has all the elements of nums between index <code>i</code> and <code>n - 1</code> <strong>(inclusive)</strong>.</li> <li>If <code>i == 0</code>, <code>nums_left</code> is <strong>empty</strong> , while <code>nums_right</code> has all the elements of <code>nums</code>.</li> <li>If <code>i == n</code>, <code>nums_left</code> has all the elements of nums, while <code>nums_right</code> is <strong>empty</strong>.</li> </ul> <p>The <strong>division score</strong> of an index <code>i</code> is the <strong>sum</strong> of the number of <code>0</code>&rsquo;s in <code>nums_left</code> and the number of <code>1</code>&rsquo;s in <code>nums_right</code>.</p> <p>Return <em><strong>all distinct indices</strong> that have the <strong>highest</strong> possible <strong>division score</strong></em>. You may return the answer in <strong>any order</strong>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> nums = [0,0,1,0]</p> <p><strong>Output:</strong> [2,4]</p> <p><strong>Explanation:</strong> Division at index</p> <ul> <li> <p>0: nums_left is []. nums_right is [0,0, <strong>1</strong> ,0]. The score is 0 + 1 = 1.</p> </li> <li> <p>1: nums_left is [<strong>0</strong> ]. nums_right is [0, <strong>1</strong> ,0]. The score is 1 + 1 = 2.</p> </li> <li> <p>2: nums_left is [<strong>0</strong> , <strong>0</strong> ]. nums_right is [<strong>1</strong> ,0]. The score is 2 + 1 = 3.</p> </li> <li> <p>3: nums_left is [<strong>0</strong> , <strong>0</strong> ,1]. nums_right is [0]. The score is 2 + 0 = 2.</p> </li> <li> <p>4: nums_left is [<strong>0</strong> , <strong>0</strong> ,1, <strong>0</strong> ]. nums_right is []. The score is 3 + 0 = 3.</p> </li> </ul> <p>Indices 2 and 4 both have the highest possible division score 3.</p> <p>Note the answer [4,2] would also be accepted.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> nums = [0,0,0]</p> <p><strong>Output:</strong> [3]</p> <p><strong>Explanation:</strong> Division at index</p> <ul> <li> <p>0: nums_left is []. nums_right is [0,0,0]. The score is 0 + 0 = 0.</p> </li> <li> <p>1: nums_left is [<strong>0</strong> ]. nums_right is [0,0]. The score is 1 + 0 = 1.</p> </li> <li> <p>2: nums_left is [<strong>0</strong> , <strong>0</strong> ]. nums_right is [0]. The score is 2 + 0 = 2.</p> </li> <li> <p>3: nums_left is [<strong>0</strong> , <strong>0</strong> , <strong>0</strong> ]. nums_right is []. The score is 3 + 0 = 3.</p> </li> </ul> <p>Only index 3 has the highest possible division score 3.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> nums = [1,1]</p> <p><strong>Output:</strong> [0]</p> <p><strong>Explanation:</strong> Division at index</p> <ul> <li> <p>0: nums_left is []. nums_right is [<strong>1</strong> , <strong>1</strong> ]. The score is 0 + 2 = 2.</p> </li> <li> <p>1: nums_left is [1]. nums_right is [<strong>1</strong> ]. The score is 0 + 1 = 1.</p> </li> <li> <p>2: nums_left is [1,1]. nums_right is []. The score is 0 + 0 = 0.</p> </li> </ul> <p>Only index 0 has the highest possible division score 2.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == nums.length</code></li> <li><code>1 <= n <= 10⁵</code></li> <li><code>nums[i]</code> is either <code>0</code> or <code>1</code>.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
List<Integer>	maxScoreIndices(int[] nums)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

maxScoreIndices

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