Find the Maximum Number of Marked Indices solution and explanation
9 more videos on this problem
2576. Find the Maximum Number of Marked Indices | LeetCode Medium | LeetCode Weekly Contest 334Deep Tech · 10:22 · 849 views
Find the Maximum Number of Marked Indices | How to reach 2 pointers solution? | Weekly Contest 334codingMohan · 22:06 · 647 views
Find the Maximum Number of Marked Indices | leetcode Weekly 334 | Leetcode MediumBinaryMagic · 12:42 · 629 views
C. Find the Maximum Number of Marked Indices - LEETCODE WEEKLY CONTEST 334 (Code + Explanation)Joyjit Codes · 6:30 · 545 views
2576. Find the Maximum Number of Marked Indices (Leetcode Medium)Programming Live with Larry · 10:57 · 461 views
Leetcode Weekly contest 334 - Medium - Find the Maximum Number of Marked IndicesPrakhar Agrawal · 7:46 · 448 views
Leetcode Weekly Contest 334 | 2576 : Find The Maximum Number Of Marked Indices Solution | In HindiCoding Community | Newton School · 9:43 · 422 views
Leetcode 2576: Find the Maximum Number of Marked Indices | Weekly Contest 334Algorithms Casts · 14:49 · 371 views
【每日一题】LeetCode 2576. Find the Maximum Number of Marked IndicesHuifeng Guan · 9:25 · 355 views
2576. Find the Maximum Number of Marked Indices - JAVA - Weekly Contest 334 (Detailed explanation)Sourin Majumdar · 7:56 · 294 views
The problem
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
iandjsuch that2 * nums[i] <= nums[j], then markiandj.
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
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.
def maxMarkedIndices(nums):
nums.sort()
count = 0
start, mid = 0, len(nums) // 2
while start < len(nums) // 2 and mid < len(nums):
if 2 * nums[start] <= nums[mid]:
count += 2
start += 1
mid += 1
return count
print(maxMarkedIndices([9, 2, 5, 4])) # Output: 4import java.util.Arrays;
public class Solution {
public int maxMarkedIndices(int[] nums) {
Arrays.sort(nums);
int count = 0;
int start = 0, mid = nums.length / 2;
while (start < nums.length / 2 && mid < nums.length) {
if (2 * nums[start] <= nums[mid]) {
count += 2;
start++;
}
mid++;
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {9, 2, 5, 4};
System.out.println(sol.maxMarkedIndices(nums)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxMarkedIndices(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int count = 0;
int start = 0, mid = nums.size() / 2;
while (start < nums.size() / 2 && mid < nums.size()) {
if (2 * nums[start] <= nums[mid]) {
count += 2;
start++;
}
mid++;
}
return count;
}
int main() {
std::vector<int> nums = {9, 2, 5, 4};
std::cout << maxMarkedIndices(nums) << std::endl; // Output: 4
return 0;
}function maxMarkedIndices(nums) {
nums.sort((a, b) => a - b);
let count = 0;
let start = 0, mid = Math.floor(nums.length / 2);
while (start < Math.floor(nums.length / 2) && mid < nums.length) {
if (2 * nums[start] <= nums[mid]) {
count += 2;
start++;
}
mid++;
}
return count;
}
console.log(maxMarkedIndices([9, 2, 5, 4])); // Output: 4#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxMarkedIndices(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int count = 0;
int start = 0, mid = numsSize / 2;
while (start < numsSize / 2 && mid < numsSize) {
if (2 * nums[start] <= nums[mid]) {
count += 2;
start++;
}
mid++;
}
return count;
}
int main() {
int nums[] = {9, 2, 5, 4};
int result = maxMarkedIndices(nums, 4);
printf("%d\n", result); // Output: 4
return 0;
}using System;
public class Solution {
public int MaxMarkedIndices(int[] nums) {
Array.Sort(nums);
int count = 0;
int start = 0, mid = nums.Length / 2;
while (start < nums.Length / 2 && mid < nums.Length) {
if (2 * nums[start] <= nums[mid]) {
count += 2;
start++;
}
mid++;
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {9, 2, 5, 4};
Console.WriteLine(sol.MaxMarkedIndices(nums)); // Output: 4
}
}This Python solution sorts the list and uses two iterators: one starting from the beginning and another from the midpoint. Each valid pair increments the count by 2.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1).
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.
def maxMarkedIndices(nums):
nums.sort()
count = 0
j = 0
for i in range(len(nums) // 2):
while j < len(nums) and 2 * nums[i] > nums[j]:
j += 1
if j < len(nums):
count += 2
j += 1
return count
print(maxMarkedIndices([9, 2, 5, 4])) # Output: 4import java.util.Arrays;
public class Solution {
public int maxMarkedIndices(int[] nums) {
Arrays.sort(nums);
int count = 0;
int j = 0;
for (int i = 0; i < nums.length / 2; ++i) {
while (j < nums.length && 2 * nums[i] > nums[j]) {
++j;
}
if (j < nums.length) {
count += 2;
j++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {9, 2, 5, 4};
System.out.println(sol.maxMarkedIndices(nums)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxMarkedIndices(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int count = 0;
int j = 0;
for (int i = 0; i < nums.size() / 2; ++i) {
while (j < nums.size() && 2 * nums[i] > nums[j]) {
++j;
}
if (j < nums.size()) {
count += 2;
j++;
}
}
return count;
}
int main() {
std::vector<int> nums = {9, 2, 5, 4};
std::cout << maxMarkedIndices(nums) << std::endl; // Output: 4
return 0;
}function maxMarkedIndices(nums) {
nums.sort((a, b) => a - b);
let count = 0;
let j = 0;
for (let i = 0; i < Math.floor(nums.length / 2); ++i) {
while (j < nums.length && 2 * nums[i] > nums[j]) {
++j;
}
if (j < nums.length) {
count += 2;
j++;
}
}
return count;
}
console.log(maxMarkedIndices([9, 2, 5, 4])); // Output: 4#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxMarkedIndices(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int count = 0;
int j = 0;
for (int i = 0; i < numsSize / 2; ++i) {
while (j < numsSize && 2 * nums[i] > nums[j]) {
++j;
}
if (j < numsSize) {
count += 2;
j++; // move j for the next possible pair
}
}
return count;
}
int main() {
int nums[] = {9, 2, 5, 4};
int result = maxMarkedIndices(nums, 4);
printf("%d\n", result); // Output: 4
return 0;
}using System;
public class Solution {
public int MaxMarkedIndices(int[] nums) {
Array.Sort(nums);
int count = 0;
int j = 0;
for (int i = 0; i < nums.Length / 2; ++i) {
while (j < nums.Length && 2 * nums[i] > nums[j]) {
++j;
}
if (j < nums.Length) {
count += 2;
j++;
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {9, 2, 5, 4};
Console.WriteLine(sol.MaxMarkedIndices(nums)); // Output: 4
}
}This Python method implements a greedy logic as described earlier. With sorting and a single-position checking j, marked pairs get counted rapidly irrespective of the original array arrangement.
Time Complexity: O(n log n) mainly from sorting.
Space Complexity: O(1).
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.
function maxNumOfMarkedIndices(nums: number[]): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let i = 0;
for (let j = (n + 1) >> 1; j < n; ++j) {
if (nums[i] * 2 <= nums[j]) {
++i;
}
}
return i * 2;
}func maxNumOfMarkedIndices(nums []int) (ans int) {
sort.Ints(nums)
i, n := 0, len(nums)
for _, x := range nums[(n+1)/2:] {
if nums[i]*2 <= x {
i++
}
}
return i * 2
}impl Solution {
pub fn max_num_of_marked_indices(mut nums: Vec<i32>) -> i32 {
nums.sort();
let mut i = 0;
let n = nums.len();
for j in (n + 1) / 2..n {
if nums[i] * 2 <= nums[j] {
i += 1;
}
}
(i * 2) as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-pointer Technique on Sorted Array | Time Complexity: O(n log n) for sorting. |
| Greedy Approach | Time Complexity: O(n log n) mainly from sorting. |
| Greedy + Two Pointers | – |
Complexity analysis
| 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. |
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.