💬 Discord
Sign In
NeetCode #525LC-2558EasyHeap / Priority Queue
← Back to All Problems

#525 · #2558 · Take Gifts From the Richest Pile(从数量最多的堆取走礼物)

📌 Problem Statement & Constraints

You are given an integer array gifts where gifts[i] is the number of gifts in the i-th pile, and an integer k. Each second you take the floor of the square root of the largest pile. Return the total number of gifts remaining after k seconds. Constraints: 1 <= gifts.length, k <= 10^3, 1 <= gifts[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. A max-heap of the pile sizes lets you take the largest pile in O(log n).
  2. Replace it with floor(sqrt(g)), which is computed exactly with math.isqrt.
  3. Repeat k times.
  4. The answer is the sum of the heap at the end.

💻 Benchmark Python3 Implementation

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        import heapq
        from math import isqrt
        h = [-g for g in gifts]            # max-heap via negation
        heapq.heapify(h)
        for _ in range(k):
            g = -heapq.heappop(h)          # the largest pile
            heapq.heappush(h, -isqrt(g))   # floor of the square root
        return -sum(h)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((n + k) log n): each of the k seconds costs one heap operation.
💾 Space Complexity
O(n) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Using int(g 0.5)**: floating-point precision fails for values near 10^9; math.isqrt is exact.
  • Using round or ceil: the operation takes the floor of the square root.
  • Sorting and re-sorting each second: O(k n log n).
  • Summing the negated heap incorrectly: remember to negate back when summing.