Watch 10 video solutions for Find the Maximum Number of Marked Indices, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Deep Tech has 843 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |