Find the Maximum Number of Marked Indices

Find the Maximum Number of Marked Indices - 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 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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: We can mark indices 2 and 3 since 2 * nums[2] = 2 * 2 = 4 ≤ nums[3] = 4. No other valid pairs exist.

Example 2 — Multiple Pairs Possible

$ Input: nums = [1,3,2,4]

› Output: 2

💡 Note: We can mark indices 0 and 1 since 2 * nums[0] = 2 * 1 = 2 ≤ nums[1] = 3. Alternatively, we could mark indices 2 and 3 since 2 * nums[2] = 2 * 2 = 4 ≤ nums[3] = 4. Both give 2 marked indices.

Example 3 — No Valid Pairs

$ Input: nums = [7,6,8]

› Output: 0

💡 Note: No pair (i,j) exists where 2 * nums[i] ≤ nums[j], so no indices can be marked.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

[3,5,2,4] - find pairs satisfying condition

Valid Pairs

Check all pairs (i,j) where 2*nums[i] ≤ nums[j]

Maximum Marked

Return maximum number of indices that can be marked

Key Takeaway

🎯 Key Insight: Sorting enables greedy two-pointer matching for optimal pairing

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to sort the array first, then use a greedy two-pointer approach. We try to pair each smaller element with the smallest possible larger element that satisfies the condition 2*nums[i] ≤ nums[j]. Best approach is Sort + Two Pointers. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Greedy with Binary Search	O(n log n)	O(n)	Sort array and use binary search to find optimal matches for each element
Brute Force - Try All Combinations	O(2^n)	O(n)	Try every possible way to pair elements and find maximum marked indices
Sort + Two Pointers	O(n log n)	O(1)	Sort array first, then use two pointers to greedily match pairs

Optimized Greedy with Binary Search — Algorithm Steps

Sort the array in ascending order
For each element in first half, use binary search to find smallest valid partner in second half
Mark both elements and continue with remaining unmarked elements
Count total marked elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Index

Sort while tracking original indices

Greedy Search

For each unmarked element, find smallest valid partner

Optimal Result

Maximize total marked indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int val, idx;
} Pair;

int compare(const void* a, const void* b) {
    Pair* pa = (Pair*)a;
    Pair* pb = (Pair*)b;
    return pa->val - pb->val;
}

int solution(int* nums, int n) {
    Pair* indexedNums = malloc(n * sizeof(Pair));
    for (int i = 0; i < n; i++) {
        indexedNums[i].val = nums[i];
        indexedNums[i].idx = i;
    }
    
    qsort(indexedNums, n, sizeof(Pair), compare);
    
    bool* marked = calloc(n, sizeof(bool));
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        if (marked[i]) continue;
        
        int val = indexedNums[i].val;
        long long target = 2LL * val;
        
        // Find the smallest element >= target that's not marked
        for (int j = i + 1; j < n; j++) {
            if (!marked[j] && indexedNums[j].val >= target) {
                marked[i] = marked[j] = true;
                count += 2;
                break;
            }
        }
    }
    
    free(indexedNums);
    free(marked);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ']' && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), and each of n elements does binary search in O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Need array to track which elements are marked

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Greedy with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler