Find The Maximum Number Of Marked Indices
01 · Problem
You are given an integer array nums. Initially every index is unmarked.
You may repeat the following move any number of times: choose two different, currently unmarked indices i and j such that 2 * nums[i] <= nums[j], and mark both of them.
Return the largest possible number of marked indices after performing moves optimally. Because indices are always marked in pairs, the answer is always even.
02 · Examples
nums = [1,6,3,2,8]
4
Pair value 1 with 3 (2 <= 3) and value 2 with 6 (4 <= 6). The 8 has no partner left, so 4 indices are marked.
nums = [4,1,9,2]
4
Pair value 1 with 4 (2 <= 4) and value 2 with 9 (4 <= 9). All four indices are marked.
nums = [10,15,12]
0
The smallest value doubled is 20, which is larger than every other value, so no pair can be formed.
03 · Constraints
- 011 <= nums.length <= 105
- 021 <= nums[i] <= 109
- 03nums is not necessarily sorted and may contain duplicate values
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.