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:
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 <= 1051 <= nums[i] <= 109
Problem Overview: You receive an integer array nums. You can mark two different indices i and j if 2 * nums[i] <= nums[j]. Each index can be used only once. The goal is to maximize the total number of marked indices.
The challenge is pairing small numbers with sufficiently large numbers without reusing indices. Since every valid pair contributes exactly two marked indices, the problem reduces to forming the maximum number of valid pairs.
Approach 1: Two-Pointer Technique on Sorted Array (O(n log n) time, O(1) extra space)
Sort the array first. After sorting, the smallest numbers are the best candidates for the left side of the inequality 2 * nums[i] <= nums[j]. Split the array conceptually into two halves and use two pointers: one pointer scans the smaller half while the second scans the larger half. If 2 * nums[left] <= nums[right], a valid pair is formed, so both pointers move forward and the count increases by two. Otherwise, move the right pointer to search for a larger value. Sorting ensures the inequality check works monotonically, making the scan linear after the sort. Total complexity becomes O(n log n) due to sorting and O(1) extra space. This technique relies heavily on patterns from Two Pointers and Sorting.
Approach 2: Greedy Pairing with Binary Search on Pair Count (O(n log n) time, O(1) space)
Another way to reason about the problem is to guess how many pairs can exist. If you try forming k pairs, check whether the smallest k elements can be matched with the largest k elements while satisfying 2 * nums[i] <= nums[j]. Because the array is sorted, you only need to compare aligned positions from the two groups. Use binary search on k between 0 and n/2. Each feasibility check scans at most k elements. Sorting dominates the runtime, keeping overall complexity at O(n log n) time and O(1) extra space. The strategy combines Greedy pairing logic with Binary Search on the answer.
Recommended for interviews: The sorted two-pointer solution is what interviewers usually expect. It demonstrates recognition of a greedy pairing pattern and efficient scanning after sorting. A brute-force attempt would check all possible pairs and quickly becomes quadratic, which signals the need for ordering and pointer movement. Showing the two-pointer method proves you understand how sorting enables linear-time pairing decisions.
Sort the array and use a two-pointer technique. One pointer starts from the beginning (smallest number) and the other from the midpoint or after-half (potential valid pair). With this setup, try to pair numbers such that 2 * nums[i] <= nums[j]. As you find pairs, move both pointers inward.
This C solution sorts the array first. It uses two pointers: one starting from the beginning of the array and another from the midpoint. For each valid pair where 2 * nums[start] is less than or equal to nums[mid], it marks the indices and moves both pointers. The end result is the maximum count of marked indices.
Time Complexity: O(n log n) due to sorting, and O(n) for the two-pointer traversal, resulting in O(n log n).
Space Complexity: O(1), since we are using a constant amount of extra space.
Sort the array and iterate through possible pairs with a greedy manner. You loop through all elements while maintaining a pointer for the current valid j that matches the condition 2 * nums[i] <= nums[j]. As soon as a match is found, increase the count.
The C solution sorts the array, then greedily attempts to mark the maximum possible pairs. It moves a single forward pointer j that checks for the current valid pair for index i. Upon finding, it increments the match count and makes the forward pointer advance.
Time Complexity: O(n log n) due to sorting and O(n) for single traversal.
Space Complexity: O(1).
According to the problem description, the problem can generate at most n / 2 pairs of indices, where n is the length of the array nums.
To mark as many indices as possible, we can sort the array nums. Next, we traverse each element nums[j] in the right half of the array, using a pointer i to point to the smallest element in the left half. If nums[i] times 2 leq nums[j], we can mark the indices i and j, and move i one position to the right. Continue traversing the elements in the right half until reaching the end of the array. At this point, the number of indices we can mark is i times 2.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Two-pointer Technique on Sorted Array | Time Complexity: O(n log n) due to sorting, and O(n) for the two-pointer traversal, resulting in O(n log n). |
| Greedy Approach | Time Complexity: O(n log n) due to sorting and O(n) for single traversal. |
| Greedy + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique on Sorted Array | O(n log n) | O(1) | Best general solution. Sort the array and pair small and large values using two pointers. |
| Binary Search on Number of Pairs | O(n log n) | O(1) | Useful when reasoning about maximum feasible pairs using greedy verification. |
2576. Find the Maximum Number of Marked Indices | LeetCode Medium | LeetCode Weekly Contest 334 • Deep Tech • 843 views views
Watch 9 more video solutions →Practice Find the Maximum Number of Marked Indices with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor