2576. Find the Maximum Number of Marked Indices

Problem Description

In this problem, you have an array of integers called nums. The array uses 0-based indexing, which means the first element is at index 0. Your goal is to maximize the number of indices that are marked following a specific rule.

The rule allows you to pick two different unmarked indices i and j such that the value at i is not more than half of the value at j (specifically, 2 * nums[i] <= nums[j]). Once you find such a pair (i and j), you can mark both indices.

The key task is to keep performing this operation as many times as you want to maximize the count of marked indices. The problem is asking you to return just this maximum count.

Intuition

To solve this problem, we can think of pairing smaller numbers with larger numbers that are at least twice their value. To simplify the process of finding pairs, we can sort the array nums. Once the array is sorted, we only need to consider each number once as a potential smaller number in a pair.

The sorted array guarantees that if a number can be paired, it must be paired with a number that comes after it. So, we can use the two-pointer approach to keep track of potential pairs. One pointer (i) starts at the beginning of the array, and the other pointer (j) starts in the middle (specifically at (n + 1) // 2, since this ensures j starts from the second half of the array and we can always find a pair such that 2 * nums[i] <= nums[j] if possible).

Then, we iterate through the array in a while loop, increasing j until we find a number that is at least twice nums[i] in value. If we find such a j, we increment the count (ans) by 2 because we can mark both indices i and j. Then we move both pointers forward to try to find the next pair.

We continue doing this until j reaches the end of the array, and by that time, ans will have the maximum number of indices that can be marked.

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution involves sorting the input array nums to easily find pairs where one number is at least double the other. Sorting is an integral part of the algorithm because it arranges the numbers in ascending order, allowing us to work with the smallest and largest numbers without having to scan the entire array each time.

After sorting, a two-pointer technique is used. This involves initializing two pointers: i at the start of the array and j at the midpoint of the array. This positioning helps to find pairs'satisfying the 2 * nums[i] <= nums[j] condition efficiently.

The solution uses a while loop to iterate through the array starting with the pointers at their initial positions:

1nums.sort()
2n = len(nums)
3i, j = 0, (n + 1) // 2
4ans = 0
5while j < n:

In this loop, a nested while loop seeks to find a pair satisfying the condition:

1while j < n and nums[i] * 2 > nums[j]:
2    j += 1

If such a j is found within the array bounds (i.e., j < n), it increments ans by 2, marking both i and j :

1if j < n:
2    ans += 2
3i, j = i + 1, j + 1

After finding a suitable pair, both pointers are moved forward. This is because, once a number has been used in a valid pair, it cannot be used again, and since the array is sorted, we're guaranteed that there are no more numbers before i that can be paired with numbers after j.

Finally, when the outer loop concludes (meaning j has reached the end of the array), ans would have been incremented appropriately for every pair found, and the function returns ans, which at this point holds the maximum number of indices that can be marked:

1return ans

This algorithm runs in O(n log n) time complexity due to the initial sorting of the array. The rest of the operations consist of single passes through parts of the array, resulting in an O(n) complexity. Thus, sorting is the most time-consuming part of the algorithm. The space complexity is O(1), not counting the space used by the sorting algorithm, which in most implementations would be O(log n), since no extra space is used outside of the sorting operation.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose our input array is nums = [1, 2, 3, 8, 4].

Our goal is to find pairs of indices i and j where the value at index i is no more than half the value at index j, and we want to maximize the count of such indices.

1. Sort the Array: First, we sort nums. After sorting, the array looks like this: sorted_nums = [1, 2, 3, 4, 8].

2. Initialize Two Pointers: We have two pointers, i starts at index 0 and j starts at index (5 + 1) // 2 = 3 in the array.

3. Begin the Two-Pointer Approach:

   • The two pointer values are nums[i] = 1 and nums[j] = 4. Since 2 * nums[i] = 2 * 1 <= 4 = nums[j], the pair (i, j) meets the condition, so we can mark both indices. We increment ans by 2 and move both pointers forward: i to 1 and j to 4.
   • We now look at nums[i] = 2 and nums[j] = 8. Since 2 * nums[i] = 2 * 2 <= 8 = nums[j], we found another pair. We increment ans by 2 once again, making ans 4, and move both pointers forward: i to 2 and j beyond the end of the array.

4. End of the While Loop: The condition of the outer while loop, j < n, is now false because j has moved beyond the end of the array.

At this point, we can no longer form any new pairs and the process ends. The result is ans = 4, which is the maximum count of indices we can mark based on the given condition. Thus, the example array nums can have a maximum of 4 marked indices by performing the operation as described.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code has two major components contributing to its time complexity:

1. Sorting the nums list, which has a time complexity of O(n log n) where n is the length of the list.
2. A while-loop that iterates over the sorted list to count the "marked" indices. In the worst case, this loop can iterate at most n times, resulting in a time complexity of O(n).

Since step 1 is the most significant factor, the overall time complexity of the function maxNumOfMarkedIndices is dominated by the sorting step, making it O(n log n).

Space Complexity

The space complexity of the code involves:

1. The sorted nums list. If the sorting is done in-place (as is usual with Python's sort methods), there's a constant space complexity of O(1).
2. The use of a fixed number of auxiliary variables like i, j, n, and ans, which contribute a constant amount of additional space, also results in O(1).

Hence, the total space complexity of the function maxNumOfMarkedIndices is O(1), reflecting that it operates in constant space outside of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.