Find the Maximum Number of Marked Indices

Medium
856.

Find the Maximum Number of Marked Indices

Find the Maximum Number of Marked Indices is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxNumOfMarkedIndices = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Maximum Number of Marked Indices — Solution

Find the Maximum Number of Marked Indices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Maximum Number of Marked Indices is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Swiggy interviews.

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

Hints for Find the Maximum Number of Marked Indices

  1. Hint 1

    Sort the array; then the smaller of each pair should come from the small half and the larger from the big half.

  2. Hint 2

    Match the smallest unused value from the first half against the first big-half value that is at least twice it.

  3. Hint 3

    Sweep the second half with one pointer over the first half.

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

  1. Sort nums.
  2. Set i = 0 and sweep j from n / 2 to n - 1.
  3. Whenever 2 · a[i] <= a[j], pair them: advance i and count the pair.
  4. 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

Java

public static int maxNumOfMarkedIndices(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length, i = 0, count = 0;
    for (int j = n / 2; j < n; j++) {
        if (2L * a[i] <= a[j]) {
            i++;
            count++;
        }
    }
    return 2 * count;
}

C++

int maxNumOfMarkedIndices(vector<int>& nums) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int n = (int) a.size(), i = 0, count = 0;
    for (int j = n / 2; j < n; j++) {
        if (2LL * a[i] <= a[j]) {
            i++;
            count++;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms