# Find the Maximum Number of Marked Indices
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-number-of-marked-indices)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-number-of-marked-indices
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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.

**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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force with Backtracking
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.
**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.
**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.
### Explanation
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:
```java
// 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;
}
```
### 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 condition `2 * 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)`.

## Binary Search on the Answer
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`.
**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).
**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 `k` is 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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- The number of pairs `k` can range from `0` to `n / 2`. We can binary search for the optimal `k` in this range.
- Create a helper function `check(k)` that returns `true` if `k` pairs can be formed, and `false` otherwise.
- To implement `check(k)`, we greedily try to pair the `k` smallest elements (`nums[0...k-1]`) with the `k` largest elements (`nums[n-k...n-1]`).
- A pairing is possible if and only if `2 * nums[i] <= nums[n-k+i]` for all `i` from `0` to `k-1`.
- The `check(k)` function iterates from `i = 0` to `k-1` and verifies this condition.
- In the main binary search loop:
  - If `check(mid)` is true, it means `mid` pairs are possible, so we try for more: `ans = mid`, `low = mid + 1`.
  - If `check(mid)` is false, `mid` is too large, so we search for a smaller `k`: `high = mid - 1`.
- The final result is `2 * ans`.

## Greedy Two-Pointer Approach
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.
**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.
**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.
### Explanation
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 both `i` and `j`. 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 for `nums[i]`. Since `nums[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 discard `nums[j]` as a potential partner and try the next element in the second half by incrementing `j`.

This process continues until we run out of elements in one of the halves.

```java
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;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Let `n` be the length of `nums`.
- Initialize a left pointer `i = 0` and a right pointer `j = n / 2`.
- Initialize a counter for pairs, `count = 0`.
- Iterate while `i` is in the first half (`i < n / 2`) and `j` is 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 for `nums[i]`. We need a larger element from the second half, so we only advance the right pointer (`j++`).
- The loop terminates when either pointer goes out of its respective half.
- The total number of marked indices is `count * 2`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```