Problem Description

You have an integer array nums with 0-based indexing. Initially, none of the indices in the array are marked.

You can perform the following operation any number of times:

• Select two different unmarked indices i and j where 2 * nums[i] <= nums[j]
• Mark both indices i and j

Your goal is to find the maximum number of indices you can mark by repeatedly applying this operation.

For example, if you have an array where you can form pairs such that one element is at least double the other, you mark both indices in each pair. The challenge is to strategically choose which indices to pair together to maximize the total number of marked indices.

The key constraint is that once an index is marked, it cannot be used in another pairing operation. Each index can only be marked once, and you must satisfy the condition 2 * nums[i] <= nums[j] for each pair you create.

Intuition

The first observation is that we can mark at most n indices total, which means we can form at most n/2 pairs since each pair marks exactly 2 indices.

To maximize the number of pairs, we should think about how to efficiently match smaller numbers with larger numbers. If we sort the array first, we get all elements in increasing order. This helps us systematically find valid pairings.

The key insight is to divide the sorted array into two halves. Why? Because if we're going to form n/2 pairs (the maximum possible), we need n/2 smaller elements and n/2 larger elements. The natural division is to consider the left half as potential "smaller" elements and the right half as potential "larger" elements in our pairs.

For each element in the right half, we want to pair it with the smallest available element from the left half that satisfies our condition. This greedy approach works because:

1. If a smaller element nums[i] can pair with a larger element nums[j], it can also pair with any element larger than nums[j]
2. By using the smallest available element for each pairing, we preserve larger elements in the left half for future pairings that might have stricter requirements

The strategy is to iterate through the right half (starting from nums[(n+1)/2]) and for each element, try to pair it with the smallest unpaired element from the left half. We use a pointer i starting at index 0 to track our position in the left half. When we find a valid pair where nums[i] * 2 <= nums[j], we move the pointer forward. The total number of successful pairings multiplied by 2 gives us the maximum number of marked indices.

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation uses a greedy algorithm with two pointers to find the maximum number of marked indices.

Step 1: Sort the array

nums.sort()

First, we sort the array in ascending order. This allows us to systematically match smaller elements with larger elements.

Step 2: Initialize pointers

i, n = 0, len(nums)

We initialize pointer i to 0, which will track our position in the left half of the array. Variable n stores the length of the array.

Step 3: Iterate through the right half

for x in nums[(n + 1) // 2 :]:

We iterate through each element in the right half of the sorted array. The starting index (n + 1) // 2 ensures we're looking at the larger half of elements. For odd-length arrays, this gives us the smaller right half, which is optimal since we can form at most n // 2 pairs.

Step 4: Greedy pairing

if nums[i] * 2 <= x:
    i += 1

For each element x in the right half, we check if the current smallest unpaired element from the left half (at index i) satisfies the condition nums[i] * 2 <= x. If it does, we can form a valid pair, so we increment i to move to the next element in the left half. If the condition isn't satisfied, we skip this element in the right half and move to the next one, keeping i unchanged.

Step 5: Return the result

return i * 2

The variable i represents the number of successful pairs we formed. Since each pair marks 2 indices, we return i * 2 as the maximum number of marked indices.

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) if we don't count the sorting space.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm works.

Example: nums = [9, 2, 5, 4]

Step 1: Sort the array After sorting: nums = [2, 4, 5, 9]

Step 2: Divide conceptually into two halves

• Left half (potential smaller elements): [2, 4] (indices 0-1)
• Right half (potential larger elements): [5, 9] (indices 2-3)

Step 3: Initialize pointer i = 0 This pointer will track our position in the left half.

Step 4: Iterate through the right half and try to form pairs

Iteration 1: Consider x = 5 (first element of right half)

• Check if nums[0] * 2 <= 5
• Check: 2 * 2 = 4 <= 5 ✓
• We can form a pair (2, 5)
• Increment i to 1

Iteration 2: Consider x = 9 (second element of right half)

• Check if nums[1] * 2 <= 9
• Check: 4 * 2 = 8 <= 9 ✓
• We can form a pair (4, 9)
• Increment i to 2

Step 5: Calculate result

• We formed i = 2 pairs
• Each pair marks 2 indices
• Maximum marked indices = 2 * 2 = 4

Final answer: 4

All indices can be marked by forming the pairs (2, 5) and (4, 9).

Another Example: nums = [3, 5, 2, 4]

After sorting: nums = [2, 3, 4, 5]

• Left half: [2, 3]
• Right half: [4, 5]

Iteration 1: x = 4

• Check: 2 * 2 = 4 <= 4 ✓
• Form pair (2, 4), increment i to 1

Iteration 2: x = 5

• Check: 3 * 2 = 6 <= 5 ✗
• Cannot form a pair, i stays at 1

Result: 1 * 2 = 2 indices marked (only the pair (2, 4))

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n × log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which uses Timsort algorithm with O(n × log n) time complexity. The subsequent for loop iterates through at most n/2 elements with constant time operations inside, contributing O(n), which doesn't affect the overall complexity.

The space complexity is O(log n). While the sorting operation is performed in-place and doesn't require additional space proportional to the input size, the sorting algorithm (Timsort) uses O(log n) space for its recursive call stack during the merge operations. The remaining operations use only O(1) additional space for variables i and n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Splitting Strategy

Problem: A common mistake is trying to pair elements arbitrarily or using a different splitting point. For example, some might try to pair the smallest element with the largest, second smallest with second largest, etc., or use a different split point like n // 2 instead of (n + 1) // 2.

Why it fails: Using n // 2 for odd-length arrays would start the right pointer at a suboptimal position. For example, with array [1, 2, 3], using n // 2 = 1 would only check elements starting from index 1, missing potential pairings.

Solution: Always use (n + 1) // 2 as the split point. This ensures:

• For even-length arrays: splits exactly in half
• For odd-length arrays: the right half has fewer elements (optimal since we can form at most n // 2 pairs)

Pitfall 2: Greedy Matching Direction

Problem: Attempting to match from right to left (largest to smallest) instead of left to right, or trying to find the "best" match for each element rather than the first valid match.

Example of incorrect approach:

# Wrong: Trying to find the largest possible match for each small element
for i in range(n // 2):
    for j in range(n - 1, i, -1):
        if nums[i] * 2 <= nums[j] and not marked[j]:
            # mark i and j
            break

Why it fails: This approach might skip valid pairings that would lead to a better overall result. The greedy left-to-right matching after sorting is optimal because it preserves larger elements for future matches.

Solution: Stick to the simple greedy approach: for each element in the right half, try to match it with the leftmost unmatched element from the left half.

Pitfall 3: Off-by-One Errors in Index Calculation

Problem: Incorrectly calculating the number of pairs or marked indices, such as returning i instead of i * 2, or returning i * 2 + 1 thinking there might be an unpaired element.

Solution: Remember that:

• Each successful pairing marks exactly 2 indices
• The return value should always be even
• The variable i tracks the number of successful pairs, not the number of marked indices

Pitfall 4: Not Handling Edge Cases

Problem: Failing to consider edge cases like:

• Arrays where no pairs can be formed (e.g., [1, 1, 1, 1])
• Arrays with only 1 or 2 elements
• Arrays where all elements can be paired

Solution: The provided algorithm naturally handles these cases:

• If no pairs can be formed, i remains 0, returning 0
• Small arrays work correctly with the split point calculation
• Maximum pairing is automatically limited by the array size