3096. Minimum Levels to Gain More Points LeetCode Solution
In this guide, you will get 3096. Minimum Levels to Gain More Points LeetCode Solution with the best time and space complexity. The solution to Minimum Levels to Gain More Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Levels to Gain More Points
You are given a binary array possible of length n.
Alice and Bob are playing a game that consists of n levels. Some of the levels in the game are impossible to clear while others can always be cleared. In particular, if possible[i] == 0, then the ith level is impossible to clear for both the players. A player gains 1 point on clearing a level and loses 1 point if the player fails to clear it.
At the start of the game, Alice will play some levels in the given order starting from the 0th level, after which Bob will play for the rest of the levels.
Alice wants to know the minimum number of levels she should play to gain more points than Bob, if both players play optimally to maximize their points.
Return the minimum number of levels Alice should play to gain more points. If this is not possible, return -1.
Note that each player must play at least 1 level.
Input: possible = [1,0,1,0]
Output: 1
Explanation:
Let’s look at all the levels that Alice can play up to:
If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has -1 + 1 – 1 = -1 point.
If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 1 – 1 = 0 points, while Bob has 1 – 1 = 0 points.
If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 1 – 1 + 1 = 1 point, while Bob has -1 point.
Alice must play a minimum of 1 level to gain more points.
Example 2:
Input: possible = [1,1,1,1,1]
Output: 3
Explanation:
Let’s look at all the levels that Alice can play up to:
If Alice plays only level 0 and Bob plays the rest of the levels, Alice has 1 point, while Bob has 4 points.
If Alice plays till level 1 and Bob plays the rest of the levels, Alice has 2 points, while Bob has 3 points.
If Alice plays till level 2 and Bob plays the rest of the levels, Alice has 3 points, while Bob has 2 points.
If Alice plays till level 3 and Bob plays the rest of the levels, Alice has 4 points, while Bob has 1 point.
Alice must play a minimum of 3 levels to gain more points.
Example 3:
Input: possible = [0,0]
Output: -1
Explanation:
The only possible way is for both players to play 1 level each. Alice plays level 0 and loses 1 point. Bob plays level 1 and loses 1 point. As both players have equal points, Alice can’t gain more points than Bob.
2 <= n == possible.length <= 105
possible[i] is either 0 or 1.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3096. Minimum Levels to Gain More Points LeetCode Solution in C++
class Solution {
public:
int minimumLevels(vector<int>& possible) {
const int n = possible.size();
const vector<int> nums = getNums(possible);
vector<int> prefix(n + 1);
partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
for (int i = 1; i < n; ++i)
if (prefix[i] > prefix[n] - prefix[i])
return i;
return -1;
}
private:
vector<int> getNums(const vector<int>& possible) {
vector<int> nums;
for (const int num : possible)
nums.push_back(num == 1 ? 1 : -1);
return nums;
}
}; /* code provided by PROGIEZ */
3096. Minimum Levels to Gain More Points LeetCode Solution in Java
class Solution {
public int minimumLevels(int[] possible) {
final int n = possible.length;
final int[] nums = getNums(possible);
int[] prefix = new int[n + 1];
for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + nums[i];
for (int i = 1; i < n; ++i)
if (prefix[i] > prefix[n] - prefix[i])
return i;
return -1;
}
private int[] getNums(int[] possible) {
int[] nums = new int[possible.length];
for (int i = 0; i < possible.length; ++i)
nums[i] = possible[i] == 0 ? -1 : 1;
return nums;
}
} // code provided by PROGIEZ
3096. Minimum Levels to Gain More Points LeetCode Solution in Python
class Solution:
def minimumLevels(self, possible: list[int]) -> int:
n = len(possible)
nums = [num if num == 1 else -1 for num in possible]
prefix = list(itertools.accumulate(nums, initial=0))
for i in range(1, n):
if prefix[i] > prefix[n] - prefix[i]:
return i
return -1 # code by PROGIEZ
