Find the Maximum Number of Marked Indices — Solution
Find the Maximum Number of Marked Indices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Maximum Number of Marked Indices is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Swiggy interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google, Swiggy
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Repeatedly pick two unmarked indices i and j with 2 · nums[i] <= nums[j] and mark both.
Return the maximum number of indices that can end up marked.
Example 1
Input: nums = [3,5,2,4]
Output: 2
Explanation: Mark 2 and 4 (2 · 2 <= 4); nothing else pairs up.
Example 2
Input: nums = [9,2,5,4]
Output: 4
Explanation: Pair 2 with 5 and 4 with 9.
Example 3
Input: nums = [7,6,8]
Output: 0
Explanation: No pair satisfies the doubling condition.
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 1000000000
Hints for Find the Maximum Number of Marked Indices
Hint 1
Sort the array; then the smaller of each pair should come from the small half and the larger from the big half.
Hint 2
Match the smallest unused value from the first half against the first big-half value that is at least twice it.
Hint 3
Sweep the second half with one pointer over the first half.
How to solve Find the Maximum Number of Marked Indices
After sorting, an optimal pairing always takes the k smallest values as the 'small' side and the k largest as the 'large' side. Sweeping the upper half while advancing a pointer through the lower half matches as many as possible.
Approach
- Sort
nums. - Set
i = 0and sweepjfromn / 2ton - 1. - Whenever
2 · a[i] <= a[j], pair them: advanceiand count the pair. - Return twice the pair count.
Why it works
If k pairs are possible, they can be rearranged so that the small sides are a[0 … k-1] and the large sides a[n-k … n-1] — swapping any pair back into that shape never breaks the condition, because the small sides only get smaller and the large sides only get larger. Starting j at n / 2 is exactly the earliest index that could belong to a maximum-size large half, and the greedy match from there is optimal by the usual exchange argument.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Matching from index 0 against index 1 upwards pairs values that should have been saved for better partners.
- The answer counts indices, so it is twice the number of pairs.
- Starting
jatn / 2matters — starting at 0 lets a value pair with itself's half of the array.
Reference solution
Python
from typing import List
def maxNumOfMarkedIndices(nums: List[int]) -> int:
a = sorted(nums)
n = len(a)
i = count = 0
for j in range(n // 2, n):
if 2 * a[i] <= a[j]:
i += 1
count += 1
return 2 * countJava
public static int maxNumOfMarkedIndices(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length, i = 0, count = 0;
for (int j = n / 2; j < n; j++) {
if (2L * a[i] <= a[j]) {
i++;
count++;
}
}
return 2 * count;
}C++
int maxNumOfMarkedIndices(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = (int) a.size(), i = 0, count = 0;
for (int j = n / 2; j < n; j++) {
if (2LL * a[i] <= a[j]) {
i++;
count++;
}
}
return 2 * count;
}JavaScript
var maxNumOfMarkedIndices = function(nums) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var n = a.length;
var i = 0, count = 0;
for (var j = Math.floor(n / 2); j < n; j++) {
if (2 * a[i] <= a[j]) { i++; count++; }
}
return 2 * count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms