Find the Maximum Number of Marked Indices — Medium Problem & Solution

Repeatedly pick two unmarked indices i and j with 2 · nums[i] <= nums[j] and mark both. Return the maximum number of indices that can end up marked.

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, Two Pointers
Asked at: Amazon, Google, Swiggy
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Repeatedly pick two unmarked indices i and j with 2 · nums[i] <= nums[j] and mark both.

Return the maximum number of indices that can end up marked.

Example 1

Input: nums = [3,5,2,4]
Output: 2
Explanation: Mark 2 and 4 (2 · 2 <= 4); nothing else pairs up.

Example 2

Input: nums = [9,2,5,4]
Output: 4
Explanation: Pair 2 with 5 and 4 with 9.

Example 3

Input: nums = [7,6,8]
Output: 0
Explanation: No pair satisfies the doubling condition.

Constraints

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000000

How to solve Find the Maximum Number of Marked Indices

After sorting, an optimal pairing always takes the k smallest values as the 'small' side and the k largest as the 'large' side. Sweeping the upper half while advancing a pointer through the lower half matches as many as possible.

Approach

Sort nums.
Set i = 0 and sweep j from n / 2 to n - 1.
Whenever 2 · a[i] <= a[j], pair them: advance i and count the pair.
Return twice the pair count.

Why it works

If k pairs are possible, they can be rearranged so that the small sides are a[0 … k-1] and the large sides a[n-k … n-1] — swapping any pair back into that shape never breaks the condition, because the small sides only get smaller and the large sides only get larger. Starting j at n / 2 is exactly the earliest index that could belong to a maximum-size large half, and the greedy match from there is optimal by the usual exchange argument.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Matching from index 0 against index 1 upwards pairs values that should have been saved for better partners.
The answer counts indices, so it is twice the number of pairs.
Starting j at n / 2 matters — starting at 0 lets a value pair with itself's half of the array.

Reference solution

Python

from typing import List

def maxNumOfMarkedIndices(nums: List[int]) -> int:
    a = sorted(nums)
    n = len(a)
    i = count = 0
    for j in range(n // 2, n):
        if 2 * a[i] <= a[j]:
            i += 1
            count += 1
    return 2 * count

JavaScript

var maxNumOfMarkedIndices = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var n = a.length;
    var i = 0, count = 0;
    for (var j = Math.floor(n / 2); j < n; j++) {
        if (2 * a[i] <= a[j]) { i++; count++; }
    }
    return 2 * count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue