We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Number of Marked Indices

Number: 2712

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed integer array nums, you can repeatedly pick two different unmarked indices i and j such that 2 * nums[i] <= nums[j] and mark both indices. The task is to maximize the total number of marked indices using the allowed operations and return that maximum count.

Key Insights

  • Sorting the array simplifies the process of finding valid pairs.
  • A two-pointer or greedy strategy helps in efficiently matching smaller numbers with the next available number that is at least twice as large.
  • Splitting the sorted array into two halves and trying to pair elements from the first half with elements in the second half is a common tactic.
  • The solution is based on pairing elements greedily to maximize the number of valid operations.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) (or O(1) extra space if sorting is done in place).

Solution

The solution follows these steps:

  1. Sort the array.
  2. Use two pointers: one (left) starting at the beginning of the array and the other (right) starting roughly at the middle.
  3. For each candidate from the left pointer, find the smallest candidate from the right pointer that satisfies 2 * nums[left] <= nums[right].
  4. If a valid pair is found, increase both pointers accounting for a full pair marked.
  5. Continue until either pointer runs out of eligible elements.
  6. The maximum number of marked indices is twice the number of valid pairs found.

This two-pointer approach ensures that every time a valid pair is made, we are making a greedy choice that maximizes the overall pairing, leading to an optimal solution.

Code Solutions

# Python Solution
def maxNumOfMarkedIndices(nums):
    # First sort the array
    nums.sort()
    n = len(nums)
    # left pointer for potential smaller values, right pointer starts at the middle
    left = 0
    right = n // 2
    pairs = 0
    
    # Loop until we exhaust one of the parts
    while left < n // 2 and right < n:
        # Check if current pair is valid:
        if 2 * nums[left] <= nums[right]:
            # Valid pair found, increment pair count and move left pointer
            pairs += 1
            left += 1
            right += 1
        else:
            # Otherwise, move the right pointer to try a larger value
            right += 1
    # Each pair marks 2 indices
    return pairs * 2

# Example Usage:
print(maxNumOfMarkedIndices([3, 5, 2, 4])) # Expected output: 2
print(maxNumOfMarkedIndices([9, 2, 5, 4])) # Expected output: 4
← Back to All Questions