Skip to main content
Talentd

Find the Maximum Number of Marked Indices - Solution & Explanation

MediumArrayTwo PointersBinary SearchGreedy18 min read
Practice this problem

Problem Statement

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

 

Approach Overview

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 1: Two-pointer Technique on Sorted Array

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting and O(n) for single traversal.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: 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 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).
Space Complexity: O(1), since we are using a constant amount of extra space.

Greedy Approach

Time Complexity: O(n log n) due to sorting and O(n) for single traversal.
Space Complexity: O(1).

Greedy + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer Technique on Sorted ArrayO(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 PairsO(n log n)O(1)Useful when reasoning about maximum feasible pairs using greedy verification.

Video Solution

2576. Find the Maximum Number of Marked Indices | LeetCode Medium | LeetCode Weekly Contest 334 • Deep Tech • 849 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Number of Marked Indices easy or hard?
The problem is classified as Medium difficulty on LeetCode. The pairing rule may initially suggest brute force, but recognizing that sorting enables a greedy two-pointer scan is the key insight that makes the problem manageable.
Find the Maximum Number of Marked Indices Python/Java solution
Most implementations follow the same pattern across languages: sort the array, initialize two pointers (one in the first half and one in the second half), and move them while checking 2 * nums[left] <= nums[right]. Python, Java, C++, and C# versions differ only in syntax while maintaining the same O(n log n) complexity.
How to solve Find the Maximum Number of Marked Indices in O(n)?
Pure O(n) time is not achievable in the general case because ordering the numbers is necessary to efficiently compare small and large elements. Sorting takes O(n log n). After sorting, the pairing step with two pointers runs in O(n), which is the fastest practical solution.
What is the best approach for Find the Maximum Number of Marked Indices?
The most efficient approach sorts the array and then uses a two-pointer greedy strategy. One pointer scans the smaller half of the array while another scans the larger half to find values where 2 * nums[i] <= nums[j]. Each valid match marks two indices. The approach runs in O(n log n) time due to sorting and O(1) extra space.
Is Find the Maximum Number of Marked Indices asked at Google/Amazon/Meta?
Problems involving greedy pairing, sorting, and two-pointer scanning appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of this question test the ability to recognize when sorting simplifies inequality constraints between elements.
What data structure is used in Find the Maximum Number of Marked Indices?
The problem mainly uses arrays along with algorithmic techniques such as sorting and the two-pointer pattern. No advanced data structures are required, which makes it a good exercise in greedy reasoning and pointer manipulation.
What is the time complexity of Find the Maximum Number of Marked Indices?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a two-pointer scan forms valid pairs in O(n) time. Space complexity is O(1) if sorting is done in-place.

Ready to solve this problem?

Practice Find the Maximum Number of Marked Indices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Array Length After Pair Removals