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 innums using the above operation any number of times.

Examples

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 <= 10^5
• 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy Two Pointers

Intuition

To maximize the number of marked indices, we want to pair the smallest numbers with the largest numbers such that 2 * nums[i] <= nums[j]. Sorting the array allows us to efficiently pair the smallest available numbers with the largest possible partners using two pointers.

Approach

1. Sort the array nums in non-decreasing order.
2. Use two pointers: l starting at 0 (smallest) and r starting at n//2 (middle of the array).
3. For each l, try to find the smallest r such that 2 * nums[l] <= nums[r].
4. If such a pair is found, increment the count by 2 and move both pointers forward.
5. Continue until either pointer reaches the end.
6. Return the total count of marked indices.

Code

C++

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), l = 0, r = n/2, ans = 0;
        while(l < n/2 && r < n) {
            if(2 * nums[l] <= nums[r]) {
                ans += 2;
                ++l; ++r;
            } else {
                ++r;
            }
        }
        return ans;
    }
};

Go

func maxNumOfMarkedIndices(nums []int) int {
    sort.Ints(nums)
    n, l, r, ans := len(nums), 0, len(nums)/2, 0
    for l < n/2 && r < n {
        if 2*nums[l] <= nums[r] {
            ans += 2
            l++
            r++
        } else {
            r++
        }
    }
    return ans
}

Java

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, l = 0, r = n/2, ans = 0;
        while(l < n/2 && r < n) {
            if(2 * nums[l] <= nums[r]) {
                ans += 2;
                l++;
                r++;
            } else {
                r++;
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maxNumOfMarkedIndices(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        var l = 0; var r = n/2; var ans = 0
        while(l < n/2 && r < n) {
            if(2 * nums[l] <= nums[r]) {
                ans += 2
                l++
                r++
            } else {
                r++
            }
        }
        return ans
    }
}

Python

class Solution:
    def maxNumOfMarkedIndices(self, nums: list[int]) -> int:
        nums.sort()
        n = len(nums)
        l, r, ans = 0, n//2, 0
        while l < n//2 and r < n:
            if 2 * nums[l] <= nums[r]:
                ans += 2
                l += 1
                r += 1
            else:
                r += 1
        return ans

Rust

impl Solution {
    pub fn max_num_of_marked_indices(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        let (mut l, mut r, mut ans) = (0, n/2, 0);
        while l < n/2 && r < n {
            if 2*nums[l] <= nums[r] {
                ans += 2;
                l += 1;
                r += 1;
            } else {
                r += 1;
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    maxNumOfMarkedIndices(nums: number[]): number {
        nums.sort((a,b)=>a-b);
        const n = nums.length;
        let l = 0, r = n>>1, ans = 0;
        while(l < n>>1 && r < n) {
            if(2 * nums[l] <= nums[r]) {
                ans += 2;
                l++;
                r++;
            } else {
                r++;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), due to sorting and a single pass with two pointers.
• 🧺 Space complexity: O(1), if sorting in place, otherwise O(n) for the sort.