IT/Computer Science
[Leetcode/Sort, Heap] 2974. Minimum Number Game
Diana Kang
2025. 4. 6. 22:34
1. Sort
✅ Approach:
- Sort the array first to make it easy to remove the minimums.
- 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)