2576. Find the Maximum Number of Marked Indices

Description

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.

 

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 <= 105
  • 1 <= nums[i] <= 109

 

Solutions

Solution 1: Greedy + Two Pointers

In order to mark as many indices as possible, we can sort the array nums, and then traverse the array from left to right. For each index ii, we find the first index jj in the right half of the array that satisfies 2×nums[i]≤nums[j]2 \times nums[i] \leq nums[j], and then mark indices ii and jj. Continue to traverse the next index ii. When we have traversed the right half of the array, it means that the marking is complete, and the number of marked indices is the answer.

The time complexity is O(n×log⁡n)O(n \times \log n), and the space complexity is O(log⁡n)O(\log n). Where nn is the length of the array nums.

Python Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        for (int i = 0, j = (n + 1) / 2; j < n; ++i, ++j) {
            while (j < n && nums[i] * 2 > nums[j]) {
                ++j;
            }
            if (j < n) {
                ans += 2;
            }
        }
        return ans;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxNumOfMarkedIndices(nums []int) (ans int) {
	sort.Ints(nums)
	n := len(nums)
	for i, j := 0, (n+1)/2; j < n; i, j = i+1, j+1 {
		for j < n && nums[i]*2 > nums[j] {
			j++
		}
		if j < n {
			ans += 2
		}
	}
	return
}

TypeScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function maxNumOfMarkedIndices(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0, j = Math.floor((n + 1) / 2); j < n; ++i, ++j) {
        while (j < n && nums[i] * 2 > nums[j]) {
            ++j;
        }
        if (j < n) {
            ans += 2;
        }
    }
    return ans;
}