2576. Find the Maximum Number of Marked Indices LeetCode Solution
In this guide, you will get 2576. Find the Maximum Number of Marked Indices LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Number of Marked Indices 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 Find the Maximum Number of Marked Indices
You are given a 0-indexed integer array nums.
Initially, all of the indices are unmarked. You are allowed to make this operation any number of times:
Pick two different unmarked indices i and j such that 2 * nums[i] <= nums[j], then mark i and j.
Return the maximum possible number of marked indices in nums using the above operation any number of times.
Example 1:
Input: nums = [3,5,2,4]
Output: 2
Explanation: In the first operation: pick i = 2 and j = 1, the operation is allowed because 2 * nums[2] <= nums[1]. Then mark index 2 and 1.
It can be shown that there's no other valid operation so the answer is 2.
Example 2:
Input: nums = [9,2,5,4]
Output: 4
Explanation: In the first operation: pick i = 3 and j = 0, the operation is allowed because 2 * nums[3] <= nums[0]. Then mark index 3 and 0.
In the second operation: pick i = 1 and j = 2, the operation is allowed because 2 * nums[1] <= nums[2]. Then mark index 1 and 2.
Since there is no other operation, the answer is 4.
Input: nums = [7,6,8]
Output: 0
Explanation: There is no valid operation to do, so the answer is 0.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})
2576. Find the Maximum Number of Marked Indices LeetCode Solution in C++
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
ranges::sort(nums);
int l = 0;
int r = nums.size() / 2 + 1;
while (l < r) {
const int m = (l + r) / 2;
if (isPossible(nums, m))
l = m + 1;
else
r = m;
}
return (l - 1) * 2;
}
private:
bool isPossible(const vector<int>& nums, int m) {
for (int i = 0; i < m; ++i)
if (2 * nums[i] > nums[nums.size() - m + i])
return false;
return true;
}
}; /* code provided by PROGIEZ */
2576. Find the Maximum Number of Marked Indices LeetCode Solution in Java
class Solution {
public int maxNumOfMarkedIndices(int[] nums) {
Arrays.sort(nums);
int l = 0;
int r = nums.length / 2 + 1;
while (l < r) {
final int m = (l + r) / 2;
if (isPossible(nums, m))
l = m + 1;
else
r = m;
}
return (l - 1) * 2;
}
private boolean isPossible(int[] nums, int m) {
for (int i = 0; i < m; ++i)
if (2 * nums[i] > nums[nums.length - m + i])
return false;
return true;
}
} // code provided by PROGIEZ
2576. Find the Maximum Number of Marked Indices LeetCode Solution in Python
class Solution:
def maxNumOfMarkedIndices(self, nums: list[int]) -> int:
nums.sort()
def isPossible(m: int) -> bool:
for i in range(m):
if 2 * nums[i] > nums[-m + i]:
return False
return True
l = bisect.bisect_left(range(len(nums) // 2 + 1), True,
key=lambda m: not isPossible(m))
return (l - 1) * 2 # code by PROGIEZ
