Find the Maximum Number of Marked Indices

Problem 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.

Key Insights

• The problem requires pairing unmarked indices based on a specific condition involving their values.
• Sorting the array helps in efficiently finding pairs that satisfy the condition.
• A greedy approach works best, where we always try to form pairs starting from the smallest elements.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - since we are using a constant amount of extra space.

Solution

To solve the problem, we can follow these steps:

1. Sort the nums array.
2. Use a two-pointer technique to find valid pairs (i, j):
   • Start with one pointer at the beginning (representing the smaller value) and another pointer at the end (representing the larger value).
   • If the condition 2 * nums[i] <= nums[j] is satisfied, mark both indices and move both pointers inward.
   • If not, move the pointer for the larger value inward to find a potentially valid pair.
3. Count the number of marked indices and return the result.

Code Solutions