Untitled — Python Coding — Nerchuko Academy

Find M Largest Numbers

MEDIUM

Given a long list of unsorted numbers (potentially millions of items) and an integer m, write a function to find the m largest numbers in the list. The order of the m largest numbers in the output does not matter.

Examples:

Example 1:

Input: nums = [3, 2, 1, 5, 6, 4], m = 2
Output: [5, 6] (or [6, 5])

Example 2:

Input: nums = [1, 23, 12, 9, 30, 2, 50], m = 3
Output: [23, 30, 50] (any order)

Example 3:

Input: nums = [1, 1, 1, 1, 1], m = 3
Output: [1, 1, 1]

Constraints:

1 <= m <= nums.length <= 10⁶
-10⁹ <= nums[i] <= 10⁹
The problem implies finding m numbers; if there are duplicates among the largest, they should be included if they qualify.

Function Signature (Python):

from typing import List

class Solution:
    def findMLargest(self, nums: List[int], m: int) -> List[int]:
        # Your code here
        pass

Solution Explanation & Interview Strategy

The Goal: We have a big pile of numbers, and we want to pick out the top m largest ones. For example, if our numbers are [3, 2, 1, 5, 6, 4] and we want the m=2 largest, the answer would be [5, 6].

The challenge is to do this efficiently, especially if the "pile of numbers" (the list) is very, very large.

Approach 1: Sorting (Brute Force)

The most straightforward idea is to sort the entire list of N numbers in descending order and then pick the first m elements. Or, sort in ascending order and pick the last m elements.

from typing import List

class Solution:
    def findMLargest_sorting(self, nums: List[int], m: int) -> List[int]:
        if m <= 0:
            return []
        nums.sort(reverse=True) # Sort in descending order
        return nums[:m]          # Return the first m elements

Complexity Analysis:

Time Complexity: O(N log N), where N is the total number of elements in nums. This is dominated by the sorting step.

Space Complexity: O(1) if the sort is in-place (like Python's Timsort often is for space, or O(N) in worst case for Timsort, or O(log N) for other sorts like Quicksort stack space). If a copy is made for sorting, then O(N).

Interview Note: This is a valid but often suboptimal solution, especially if N is much larger than M. The interviewer will likely push for a more efficient approach.

Approach 2: Using a Min-Heap (Optimal for N >> M)

A more efficient approach, particularly when N (total numbers) is much larger than m (numbers to find), is to use a min-heap of size m.

Initialize an empty min-heap.
Iterate through each number num in the input list nums:
- If the heap size is less than m, add num to the heap.
- Else (if heap size is already m):
  - If num is greater than the smallest element in the heap (the root of the min-heap, heap[0]), then this num belongs among the m largest seen so far. Remove the smallest element from the heap (heapq.heappop()) and add the current num (heapq.heappush()). This can be done more efficiently with heapq.heapreplace().
After iterating through all numbers, the heap will contain the m largest numbers.

Python's heapq module implements a min-heap.

from typing import List
import heapq

class Solution:
    def findMLargest_min_heap(self, nums: List[int], m: int) -> List[int]:
        if m <= 0:
            return []
        if m > len(nums): # Or if m >= len(nums), just return sorted nums or nums itself if order doesn't matter
             # Depending on strict definition, if m > len(nums), you might return all nums
             # For this problem, usually m <= len(nums) is implied or handled by constraints.
             # If m is very large, sorting might be better.
             pass # Assuming m <= len(nums) as per typical constraints

        min_heap = []
        for num in nums:
            if len(min_heap) < m:
                heapq.heappush(min_heap, num)
            elif num > min_heap[0]: # num is larger than the smallest of the m largest found so far
                heapq.heapreplace(min_heap, num) # Pop smallest and push new num
        
        return min_heap # The heap now contains the m largest numbers

# Python's heapq also has nlargest which does this efficiently:
# return heapq.nlargest(m, nums)
# However, an interviewer will want to see the manual heap implementation logic.

# Example Usage:
# sol = Solution()
# print(sol.findMLargest_min_heap([3, 2, 1, 5, 6, 4], 2))  # Output: [5, 6] (order might vary)
# print(sol.findMLargest_min_heap([1, 23, 12, 9, 30, 2, 50], 3)) # Output: [30, 50, 23] (order might vary)

How it works (for `nums = [3, 2, 1, 5, 6, 4]`, `m = 2`):

Initialize min_heap = [].
num = 3: len(min_heap) < 2. Push 3. min_heap = [3].
num = 2: len(min_heap) < 2. Push 2. min_heap = [2, 3] (heapified).
num = 1: len(min_heap) == 2. 1 > min_heap[0] (1 > 2) is false. Do nothing.
num = 5: len(min_heap) == 2. 5 > min_heap[0] (5 > 2) is true. Replace 2 with 5. min_heap = [3, 5].
num = 6: len(min_heap) == 2. 6 > min_heap[0] (6 > 3) is true. Replace 3 with 6. min_heap = [5, 6].
num = 4: len(min_heap) == 2. 4 > min_heap[0] (4 > 5) is false. Do nothing.
Loop ends. Return min_heap (which is [5, 6] or [6, 5] after heap operations).

Complexity Analysis (Min-Heap):

Time Complexity: O(N log M). We iterate through N numbers. For each number, heap operations (push, pop, replace) take O(log M) time as the heap size is bounded by M.

Space Complexity: O(M) to store the M elements in the heap.

Key Takeaways for Interviews:

Discuss Brute Force First: Mention the O(N log N) sorting approach and its inefficiency if M is much smaller than N.
Introduce the Heap Solution: Explain why a min-heap of size M is ideal. It efficiently keeps track of the M largest elements encountered so far by always allowing quick access to the smallest of these M (the root) and efficient replacement.
Complexity Trade-off: The heap solution is O(N log M) time and O(M) space, which is better than O(N log N) time if M is small. If M is close to N (e.g., M = N/2 or M = N), then O(N log M) approaches O(N log N), and sorting might be comparable or even slightly better due to constant factors or if an in-place sort is used.
Python's `heapq` Module: Demonstrate knowledge of heapq for implementing heaps. Mentioning heapq.nlargest(m, nums) is good, but be prepared to explain the underlying min-heap logic as that's what the interviewer wants to see.
Alternative (Quickselect - Advanced): For finding the k-th largest element, Quickselect offers an average time complexity of O(N). This could be extended to find M largest, but is more complex to implement correctly during an interview. The heap solution is generally preferred for its balance of efficiency and implementation simplicity for this "top M" variant.