#2576

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find the Maximum Number of Marked Indices

Maximize marked indices in an array by performing allowed operations, applying binary search to find the optimal count efficiently.

array two pointers binary search greedy sorting

Problem Statement

Given a 0-indexed integer array nums, you can repeatedly pick two indices i and j (i < j) such that 2 * nums[i] <= nums[j] and mark both indices. Initially all indices are unmarked, and each index can only be marked once.

Return the maximum number of indices that can be marked after performing the operation any number of times. The challenge requires efficiently checking the largest k such that k operations are possible, tying directly to binary search over the valid answer space.

Examples

Example 1

Input: nums = [3,5,2,4]

Output: 2

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

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

There is no valid operation to do, so the answer is 0.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Sort and Use Two Pointers

First, sort nums to simplify the comparison 2 * nums[i] <= nums[j]. Use two pointers from start and end to pair the smallest unmarked value with the largest possible to maximize marked indices.

Binary Search over Operations

Apply binary search on the number of operations k. For each k, check if the first k smallest numbers can be paired with the last k largest numbers to satisfy 2 * nums[i] <= nums[j]. This efficiently finds the maximum feasible k.

Greedy Pairing Check

Within the binary search check, greedily pair elements from the left half and right half of the sorted array. If all pairs satisfy the condition, consider this k feasible. Otherwise, reduce k and repeat the search.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting costs O(n log n). Each binary search step takes O(n) to verify k operations, leading to O(n log n) overall. Space is O(1) if sorting in-place or O(n) for additional storage.

What Interviewers Usually Probe

Focus on pairing strategy and feasibility check for k operations.
Check how candidates apply binary search to maximize marked indices.
Listen for explanation of why greedy two-pointer pairing guarantees optimal answer.

Common Pitfalls or Variants

Common pitfalls

Failing to sort nums first, causing incorrect pairings.
Incorrectly pairing indices, violating i < j constraint or the 2*nums[i] <= nums[j] rule.
Not using binary search and trying brute-force, which is too slow for large arrays.

Follow-up variants

Change condition to 3 * nums[i] <= nums[j] and maximize marked indices.
Restrict indices to be consecutive, altering the two-pointer strategy.
Compute maximum marked indices but return the specific pairs chosen.

FAQ

What is the main pattern in Find the Maximum Number of Marked Indices?

The key pattern is binary search over the valid number of operations combined with greedy two-pointer pairing.

How do I check if k operations are possible?

Sort nums and pair the smallest k elements with the largest k elements using two pointers. If all satisfy 2 * nums[i] <= nums[j], k operations are feasible.

What is the time complexity for this approach?

Sorting takes O(n log n), and binary search with verification adds another O(n log n), giving O(n log n) overall.

Can I solve this without sorting?

Not efficiently. Sorting simplifies pairing and ensures the greedy two-pointer approach finds the maximum marked indices.

Are there edge cases to consider?

Yes. Arrays where no operation is possible return 0, and arrays where multiple pairs compete for the same indices must respect i < j and marking only once.

terminal

Solution

Solution 1: Greedy + Two Pointers

According to the problem description, the problem can generate at most $n / 2$ pairs of indices, where $n$ is the length of the array $\textit{nums}$.

1

2

3

4

5

6

7

8

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()
        i, n = 0, len(nums)
        for x in nums[(n + 1) // 2 :]:
            if nums[i] * 2 <= x:
                i += 1
        return i * 2

Continue Practicing

#2234 maximum total beauty of the gardens #2071 maximum number of tasks you can assign #2563 count the number of fair pairs