Leetcode 2155: All Divisions With the Highest Score of a Binary Array
You are given a binary array ’nums’. You can divide the array at any index ‘i’ into two parts: ’numsleft’ (before index ‘i’) and ’numsright’ (from index ‘i’ to the end). The division score is the sum of zeros in ’numsleft’ and ones in ’numsright’. Your task is to find all indices where the division score is the highest.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary array 'nums' with length 'n'.
Example: nums = [1, 0, 1, 0]
Constraints:
• 1 <= n <= 10^5
• nums[i] is either 0 or 1
Output: Return a list of indices that give the highest division score.
Example: [3]
Constraints:
• The output should contain all indices where the division score is maximum.
Goal: Iterate through all possible indices, compute the division score, and track the indices that give the highest score.
Steps:
• Count the total number of 1's in the array initially.
• Iterate through each possible division index, calculate the number of 0's in 'numsleft' and the number of 1's in 'numsright'.
• Update the highest division score and collect indices that give the highest score.
Goal: The array will have a length of at least 1 and no more than 10^5 elements, each being either 0 or 1.
Steps:
• 1 <= n <= 10^5
• nums[i] is either 0 or 1
Assumptions:
• The array 'nums' is non-empty and contains only binary values (0 or 1).
• Input: Example 1: nums = [1, 0, 1, 0]
• Explanation: The division scores at each index are calculated as follows, and the highest score is achieved at indices 3 and 4.
• Input: Example 2: nums = [0, 0, 0]
• Explanation: The division score is highest at index 3 where all 0's are left in 'numsleft' and none in 'numsright'.
Approach: To solve this problem, we calculate the division score for each index and keep track of the indices with the maximum score.
Observations:
• The number of 1's in 'numsright' decreases as we move through the array, while the number of 0's in 'numsleft' increases.
• We can track the number of zeros and ones as we iterate through the array to efficiently calculate the division score.
Steps:
• Calculate the initial number of 1's in the array.
• Iterate over each possible division point, keeping track of the number of 0's in 'numsleft' and the number of 1's in 'numsright'.
• For each index, calculate the division score and update the highest score if necessary.
Empty Inputs:
• The array is non-empty, so no special handling for empty arrays is needed.
Large Inputs:
• For very large arrays (up to 10^5 elements), the solution should be efficient enough to run in O(n) time.
Special Values:
• Arrays that consist entirely of 0's or 1's will still work as expected.
Constraints:
• Ensure that the solution handles large inputs within the time limits.
vector<int> maxScoreIndices(vector<int>& nums) {
int n = nums.size();
int ones = 0;
for(int i = 0; i < n; i++)
if (nums[i] == 1) ones++;
int mx = ones;
vector<int> mxx;
mxx.push_back(0);
int zeros = 0;
int prv, cur = mx;
for(int i = 1; i < n + 1; i++) {
zeros += ((nums[i - 1] == 0)? 1 : 0);
ones -= ((nums[i - 1] == 1)? 1 : 0);
prv = mx;
cur = zeros + ones;
mx = max(mx, cur);
if (mx == cur && cur == prv) mxx.push_back(i);
else if (mx > prv) {
mxx.clear();
mxx.push_back(i);
}
}
return mxx;
}
1 : Function Declaration
vector<int> maxScoreIndices(vector<int>& nums) {
The function 'maxScoreIndices' is declared with a parameter 'nums', a vector of integers, and returns a vector of integers representing the indices with maximum scores.
2 : Array Size
int n = nums.size();
Calculate the size of the 'nums' array and store it in the variable 'n'.
3 : Variable Initialization
int ones = 0;
Initialize a variable 'ones' to count the number of ones in the 'nums' array.
4 : Loop Initialization
for(int i = 0; i < n; i++)
Start a loop to iterate through all elements of the 'nums' array.
5 : Count Ones
if (nums[i] == 1) ones++;
Increment the 'ones' counter for each element in the 'nums' array that equals 1.
6 : Score Calculation
int mx = ones;
Initialize 'mx' with the value of 'ones', which will keep track of the maximum score seen so far.
7 : Vector Initialization
vector<int> mxx;
Declare a vector 'mxx' to store the indices where the maximum score is reached.
8 : Push Initial Index
mxx.push_back(0);
Push index 0 into 'mxx' as it is always a valid candidate for the maximum score.
9 : Zero Counter
int zeros = 0;
Initialize 'zeros' to count the number of zeros encountered during the loop.
10 : Previous and Current Score Initialization
int prv, cur = mx;
Initialize 'prv' and 'cur' to track the previous and current scores during the iteration.
11 : Loop Through Array
for(int i = 1; i < n + 1; i++) {
Start a loop that iterates from index 1 to 'n' (inclusive) to calculate the score at each index.
12 : Count Zeros
zeros += ((nums[i - 1] == 0)? 1 : 0);
Increment the 'zeros' counter if the current element in 'nums' is zero.
13 : Update Ones
ones -= ((nums[i - 1] == 1)? 1 : 0);
Decrement the 'ones' counter if the current element in 'nums' is one.
14 : Track Maximum Scores
prv = mx;
Store the current value of 'mx' in 'prv' to track the previous score.
15 : Current Score Calculation
cur = zeros + ones;
Calculate the current score by summing the count of zeros and ones.
16 : Update Maximum Score
mx = max(mx, cur);
Update 'mx' with the maximum of the previous score and the current score.
17 : Handle Score Ties
if (mx == cur && cur == prv) mxx.push_back(i);
If the current score is equal to both the previous and the maximum score, add the current index to the 'mxx' vector.
18 : Clear and Update Max Indices
else if (mx > prv) {
If the current score is greater than the previous score, clear the 'mxx' vector and add the current index.
19 : Push Updated Index
mxx.push_back(i);
Push the current index into the 'mxx' vector after the score is updated.
20 : Return Final Indices
return mxx;
Return the vector 'mxx' containing the indices with the maximum score.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution iterates through the array once, which is efficient for large inputs.
Best Case: O(1)
Worst Case: O(n)
Description: The solution uses a few variables to store the scores and indices, so the space complexity is O(n) in the worst case.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus