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.
A more efficient approach involves sorting the array first. We can observe that if we can form k pairs, we can also form k-1 pairs. This monotonicity allows us to binary search for the maximum possible number of pairs, k.
Algorithm
- Sort the input array
numsin non-decreasing order. - The number of pairs
kcan range from0ton / 2. We can binary search for the optimalkin this range. - Create a helper function
check(k)that returnstrueifkpairs can be formed, andfalseotherwise. - To implement
check(k), we greedily try to pair theksmallest elements (nums[0...k-1]) with theklargest elements (nums[n-k...n-1]). - A pairing is possible if and only if
2 * nums[i] <= nums[n-k+i]for allifrom0tok-1. - The
check(k)function iterates fromi = 0tok-1and verifies this condition. - In the main binary search loop:
- If
check(mid)is true, it meansmidpairs are possible, so we try for more:ans = mid,low = mid + 1. - If
check(mid)is false,midis too large, so we search for a smallerk:high = mid - 1.
- If
- The final result is
2 * ans.
Walkthrough
This approach leverages the monotonic nature of the problem. After sorting nums, if we can form k pairs, it's certain we can form any number of pairs less than k. This allows us to use binary search on the number of pairs, k, which can range from 0 to n/2.
For a given k, how do we check if it's possible to form k pairs? The best strategy is to use the k smallest numbers as the smaller elements of the pairs and the k largest numbers as the larger elements. To make the condition 2 * nums[i] <= nums[j] as easy to satisfy as possible, we should pair the smallest with the smallest available, i.e., nums[0] with nums[n-k], nums[1] with nums[n-k+1], and so on. The most restrictive condition will be 2 * nums[k-1] <= nums[n-1]. In general, we must satisfy 2 * nums[i] <= nums[n-k+i] for all i in [0, k-1].
The check(k) function implements this verification. The main function performs a binary search to find the largest k for which check(k) is true.
import java.util.Arrays; class Solution { public int maxNumOfMarkedIndices(int[] nums) { Arrays.sort(nums); int n = nums.length; int ans = 0; int low = 0, high = n / 2; while (low <= high) { int k = low + (high - low) / 2; if (k == 0) { low = k + 1; continue; } if (check(k, nums)) { ans = k; low = k + 1; } else { high = k - 1; } } return ans * 2; } private boolean check(int k, int[] nums) { int n = nums.length; for (int i = 0; i < k; i++) { if (2L * nums[i] > nums[n - k + i]) { return false; } } return true; }}Complexity
Time
O(N log N). Sorting takes O(N log N). The binary search performs O(log N) iterations, and each `check` call takes O(N) time, making the search part O(N log N). The total complexity is dominated by these two parts.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. `Arrays.sort` in Java for primitives has an average space complexity of O(log N).
Trade-offs
Pros
Correct and efficient enough to pass within the time limits.
It's a standard and powerful technique for problems where the feasibility of an answer
kis monotonic.
Cons
Slightly more complex to reason about and implement compared to the final two-pointer solution.
The constant factor on the time complexity might be higher than the two-pointer approach due to repeated checks over the array within the binary search loop.
The most optimal solution uses a greedy strategy with two pointers. After sorting the array, we can intuitively see that small numbers should be paired with large numbers. We can split the sorted array into two halves and try to pair elements from the first half with elements from the second half in a single pass.
Algorithm
- Sort the input array
numsin non-decreasing order. - Let
nbe the length ofnums. - Initialize a left pointer
i = 0and a right pointerj = n / 2. - Initialize a counter for pairs,
count = 0. - Iterate while
iis in the first half (i < n / 2) andjis in the second half (j < n):- Check if
2 * nums[i] <= nums[j]. - If true, we have found a valid pair. Increment
count, and advance both pointers (i++,j++) to look for the next pair. - If false,
nums[j]is too small fornums[i]. We need a larger element from the second half, so we only advance the right pointer (j++).
- Check if
- The loop terminates when either pointer goes out of its respective half.
- The total number of marked indices is
count * 2.
Walkthrough
This approach is based on a greedy algorithm. The key insight is that to maximize the number of pairs, we should always try to use the smallest available numbers for the nums[i] part of the condition and larger numbers for the nums[j] part. Sorting the array nums is the first step.
After sorting, we can logically divide the array into two halves: the first n/2 elements are candidates for the smaller number in a pair, and the remaining elements are candidates for the larger number.
We use two pointers: i starts at 0 (the beginning of the first half) and j starts at n/2 (the beginning of the second half). We then try to match nums[i] with nums[j].
- If
2 * nums[i] <= nums[j], we have found a valid pair. We count this pair and advance bothiandj. This is a safe greedy move because we've used the smallest available small number (nums[i]) with the smallest available large number (nums[j]) that could satisfy the condition, leaving larger numbers for the remaining, larger small numbers. - If
2 * nums[i] > nums[j],nums[j]is too small fornums[i]. Sincenums[i]is the smallest available candidate from the first half,nums[j]can't be paired with any other number from the first half either. So, we discardnums[j]as a potential partner and try the next element in the second half by incrementingj.
This process continues until we run out of elements in one of the halves.
import java.util.Arrays; class Solution { public int maxNumOfMarkedIndices(int[] nums) { Arrays.sort(nums); int n = nums.length; int i = 0; int j = n / 2; int count = 0; while (i < n / 2 && j < n) { // Use long for the multiplication to avoid overflow, as nums[i] can be large. if (2L * nums[i] <= nums[j]) { count++; i++; j++; } else { j++; } } return count * 2; }}Complexity
Time
O(N log N), which is dominated by the sorting step. The subsequent two-pointer scan is a single pass, taking O(N) time.
Space
O(log N) or O(N), for the in-place sort. If we are not allowed to modify the input array, it would be O(N) to store a copy.
Trade-offs
Pros
Most efficient solution with the best possible time complexity.
Elegant and simple to implement once the greedy strategy is understood.
Optimal in terms of constant factors as it only requires a single pass after sorting.
Cons
The correctness of the greedy strategy, while intuitive, might not be immediately obvious to prove rigorously without an exchange argument.
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; }}class Solution {public: int maxNumOfMarkedIndices(vector<int> &nums) { sort(nums.begin(), nums.end()); int n = nums.size(); 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; }};class Solution: def maxNumOfMarkedIndices(self, nums: List[int]) -> int: nums . sort() n = len(nums) i, j = 0, (n + 1) // 2 ans = 0 while j < n: while j < n and nums[i] * 2 > nums[j]: j += 1 if j < n: ans += 2 i, j = i + 1, j + 1 return ansVideo 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.