LeetCode 2576 - Find the Maximum Number of Marked Indices

This problem asks us to maximize the number of indices in an array that can be "marked" using a specific operation. You are given an integer array nums and can repeatedly pick two different unmarked indices i and j such that 2 nums[i] <= nums[j].

leetcodemediumarraytwo-pointersbinary-searchgreedysorting

LeetCode Problem 2576

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

Solution

Problem Understanding

This problem asks us to maximize the number of indices in an array that can be "marked" using a specific operation. You are given an integer array nums and can repeatedly pick two different unmarked indices i and j such that 2 * nums[i] <= nums[j]. Once selected, both indices i and j are marked. The goal is to determine the maximum number of indices that can be marked after performing this operation as many times as possible.

In simpler terms, we are pairing smaller numbers with sufficiently larger numbers to satisfy the 2 * nums[i] <= nums[j] condition. Each successful pairing marks two indices, and we want to count as many marked indices as possible.

Constraints tell us that nums can have up to 100,000 elements and numbers can be very large (<= 10^9). This implies that brute-force checking of all pairs is infeasible due to the O(n^2) time complexity.

Important edge cases include:

  • Arrays with no valid pairs, e.g., [7,6,8].
  • Arrays where multiple valid pairings exist, e.g., [9,2,5,4].
  • Arrays with repeated elements or all equal elements.

Approaches

Brute Force

A brute-force approach would iterate over all pairs (i, j) of unmarked indices and mark them whenever 2 * nums[i] <= nums[j]. We would continue until no more valid pairs exist. While this approach is correct, it has a time complexity of O(n^2), which is too slow for n = 10^5.

Optimal Approach

The key insight is that sorting the array allows us to efficiently pair smaller numbers with larger numbers using a two-pointer or greedy strategy. After sorting, the smallest numbers are at the start, and the largest are at the end. We can attempt to pair the smallest unmarked numbers with the largest numbers that satisfy the condition 2 * nums[i] <= nums[j]. This approach ensures maximal pairing because:

  • We always attempt to use the smallest available nums[i], leaving larger numbers for potential future pairings.
  • Sorting guarantees that once a number nums[i] cannot pair with nums[j], it cannot pair with any smaller nums[j] either.

Using two pointers, we iterate through the array from both ends. We count how many valid pairs can be formed and multiply by two to get the total marked indices.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate all pairs repeatedly
Optimal O(n log n) O(1) Sort array + two-pointer greedy pairing

Algorithm Walkthrough

  1. Sort the array nums in ascending order. Sorting helps us efficiently find pairs where a smaller number can pair with a larger number.
  2. Split the array into two halves: let the first half be potential i candidates (smaller numbers) and the second half be potential j candidates (larger numbers). Use integer division n // 2 to determine the split.
  3. Initialize two pointers: i starting at the beginning of the first half, and j starting at the beginning of the second half.
  4. Count valid pairs: while both pointers are within bounds, check if 2 * nums[i] <= nums[j]. If so, increment the count of valid pairs, and move both pointers forward. If the condition fails, move only the j pointer forward to find a larger number that can pair.
  5. Compute total marked indices: each valid pair marks two indices, so multiply the number of pairs by 2.

Why it works: Sorting ensures that smaller numbers are paired with the smallest sufficient larger numbers. The two-pointer strategy ensures no overlap and maximizes pairings. By iterating in order, we guarantee that no number is wasted or skipped unnecessarily.

Python Solution

from typing import List

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

Explanation: The array is first sorted to enable efficient pairing. We use two pointers to traverse the two halves, counting the number of valid pairs. The left pointer moves only when a valid pair is found, ensuring each smaller number is used at most once. The right pointer always moves, ensuring we explore all larger numbers. Multiplying the count by 2 gives the total marked indices.

Go Solution

import "sort"

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

Explanation: The Go version mirrors the Python solution. We use sort.Ints to sort the slice and two pointers to count pairs. Slice indexing and loop conditions handle boundaries safely. Multiplying by 2 yields the number of marked indices.

Worked Examples

Example 1

nums = [3,5,2,4]
Sorted: [2,3,4,5]
Left half: [2,3], Right half: [4,5]
i=0, j=2: 2*2 <= 4 -> pair, count=1, left=1, right=3
i=1, j=3: 2*3 <= 5 -> false, right++
End loop
Return 2

Example 2

nums = [9,2,5,4]
Sorted: [2,4,5,9]
Left half: [2,4], Right half: [5,9]
i=0, j=2: 2*2 <= 5 -> true, count=1, left=1, right=3
i=1, j=3: 2*4 <= 9 -> true, count=2, left=2, right=4
Return 4

Example 3

nums = [7,6,8]
Sorted: [6,7,8]
Left half: [6], Right half: [7,8]
i=0, j=1: 2*6 <= 7 -> false, j++
i=0, j=2: 2*6 <= 8 -> false, j++
End loop
Return 0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, two-pointer traversal is O(n)
Space O(1) Sorting can be done in-place, extra variables are constant

The algorithm scales efficiently for n up to 100,000 due to sorting plus linear scan.

Test Cases

# Provided examples
assert Solution().maxNumOfMarkedIndices([3,5,2,4]) == 2  # Single valid pair
assert Solution().maxNumOfMarkedIndices([9,2,5,4]) == 4  # Two valid pairs
assert Solution().maxNumOfMarkedIndices([7,6,8]) == 0    # No valid pairs

# Boundary cases
assert Solution().maxNumOfMarkedIndices([1]) == 0        # Single element
assert Solution().maxNumOfMarkedIndices([1,1]) == 0      # Cannot pair equal small numbers

# Stress case
assert Solution().maxNumOfMarkedIndices(list(range(1, 100001))) == 100000  # Fully pairable
assert Solution().maxNumOfMarkedIndices([10**9]*100000) == 0  # All equal large numbers
Test Why
[3,5,2,4] Single valid pair
[9,2,5,4] Multiple valid pairs
[7,6,8] No valid pairs
[1] Single element edge case
[1,1] Cannot pair identical small numbers
range(1,100001) Stress test, fully pairable
[10^9]*100000 All equal, no pairs possible

Edge Cases

Case 1: Single element array

An array with one element cannot form a pair, so the function correctly returns 0.

Case 2: All equal numbers

If all numbers are identical, 2 * nums[i] will never be less than or equal to any other number in the array. The algorithm handles this because the two-pointer check will always fail, returning 0.

Case 3: Large array with maximal numbers

The algorithm correctly handles nums of size up to 100,000 with values up to 10^9 because all calculations involve integer multiplication within Python or Go integer ranges. Sorting and linear traversal remain efficient.

Case 4: Odd-length arrays

Splitting the array in