Find the maximum number of marked indices

Array Two Pointers Binary Search Greedy Sorting

41.1% acceptance

Feb 25, 2026

597

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_num_of_marked_indices(mut nums: Vec<i32>) -> i32 {
    nums.sort_unstable();
    let n = nums.len();
    // Binary search for k: pairs nums[0..k-1] with nums[n-k..n-1]
    // Check: for all i in 0..k, 2*nums[i] <= nums[n-k+i]
    let can_mark = |k: usize| -> bool {
      for i in 0..k {
        if 2 * nums[i] > nums[n - k + i] {
          return false;
        }
      }
      true
    };
    let mut lo = 0usize;
    let mut hi = n / 2;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if can_mark(mid) { lo = mid; } else { hi = mid - 1; }
    }
    (lo * 2) as i32
  }
}