[Leetcode/Sort, Heap] 2974. Minimum Number Game

 

1. Sort

✅ Approach:

1. Sort the array first to make it easy to remove the minimums.
2. In every round:
   • Alice removes the smallest number (i.e., pop from the front).
   • Bob removes the next smallest number.
   • Bob appends his number first, then Alice.

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        nums.sort()
        arr = []
        while nums:
            alice = nums.pop(0)  # Alice removes min
            bob = nums.pop(0)    # Bob removes next min
            arr.append(bob)      # Bob appends first
            arr.append(alice)    # Then Alice
        return arr

 

• pop(0) removes and returns the first element (element at index 0).

🧠 Time Complexity

## 1. sort
nums.sort()            # O(n log n)
while nums:            # loop runs n/2 times (since 2 pops per iteration)
    alice = nums.pop(0)  # O(n) each time (because pop(0) shifts all elements)
    bob = nums.pop(0)    # O(n)

Sorting nums	O(n log n)
Each pop(0) inside loop	O(n)
Total pops (n times)	O(n²)

 

---

2. heap

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        heapq.heapify(nums)  # Turn nums into a min-heap
        arr = []
        while nums:
            alice = heapq.heappop(nums)  # Alice removes min
            bob = heapq.heappop(nums)    # Bob removes next min
            arr.append(bob)              # Bob appends first
            arr.append(alice)            # Then Alice
        return arr

 

🧠 Time Complexity

• heapify(nums) → O(n)
• Each heappop() → O(log n)
• Two heappop() per loop × (n/2) rounds → O(n log n)