Find the Maximum Number of Marked Indices
MedPrompt
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
iandjsuch that2 * nums[i] <= nums[j], then markiandj.
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.Example 3:
Input: nums = [7,6,8]
Output: 0
Explanation: There is no valid operation to do, so the answer is 0.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to form pairs of marked indices. We can define a recursive function that tries to form a valid pair from the currently unmarked indices, marks them, and then calls itself on the remaining unmarked indices. We use backtracking to explore all possibilities and find the one that yields the maximum number of marked indices.
Algorithm
- Define a recursive function, say
solve(marked_indices), which takes the set of currently marked indices as input. - The base case is when no more valid pairs can be formed. In this case, return 0.
- In the recursive step, iterate through all possible pairs of unmarked indices
(i, j). - If a pair
(i, j)satisfies the condition2 * nums[i] <= nums[j](or vice-versa), make a recursive call:2 + solve(marked_indices + {i, j}). - Keep track of the maximum value returned by these recursive calls.
- To avoid re-computation, memoization can be used, where the state is the set of marked indices (e.g., a bitmask).
- The initial call would be
solve(empty_set).
Walkthrough
The brute-force method systematically checks every possible combination of pairs. It uses a recursive helper function that explores the decision tree of forming pairs.
For a given set of unmarked indices, the function tries to pick two indices i and j, checks if they form a valid pair (2 * nums[i] <= nums[j]). If they do, it marks them and recursively calls itself to find the maximum pairs from the rest. If they don't, it tries another pair. This process continues until all combinations are exhausted.
The state of the recursion can be represented by a boolean array or a bitmask indicating which indices are marked. However, due to the exponential growth of possibilities, this approach is only viable for very small input sizes.
For instance, a function solve(marked_mask) would be:
// This is a conceptual illustration. It's too slow for the given constraints.// A full implementation would require a way to manage the state (marked indices)// and would be very complex.private int solve(boolean[] marked) { int max = 0; for (int i = 0; i < nums.length; i++) { if (!marked[i]) { for (int j = i + 1; j < nums.length; j++) { if (!marked[j]) { // Check both pairing possibilities if (2L * nums[i] <= nums[j] || 2L * nums[j] <= nums[i]) { marked[i] = true; marked[j] = true; max = Math.max(max, 2 + solve(marked)); marked[i] = false; // Backtrack marked[j] = false; } } } } } return max;}Complexity
Time
O(N! * N^2) or similar factorial/exponential complexity. The number of ways to choose N/2 pairs from N elements is huge.
Space
O(N), for the recursion depth, as at most N/2 recursive calls can be nested.
Trade-offs
Pros
Conceptually simple and directly follows the problem statement.
Guaranteed to find the optimal solution if it completes execution.
Cons
Extremely inefficient with a time complexity that is factorial-like.
Infeasible for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error.
The state space for memoization (2^N) is too large to be practical.
Solutions
Solution
class Solution {public int maxNumOfMarkedIndices(int[] nums) { Arrays.sort(nums); int n = nums.length; int ans = 0; for (int i = 0, j = (n + 1) / 2; j < n; ++i, ++j) { while (j < n && nums[i] * 2 > nums[j]) { ++j; } if (j < n) { ans += 2; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.