Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Take Gifts From the Richest Pile(easy)

Problem Statement

You're presented with several piles of gifts, with each pile containing a certain number of gifts. Every second, you'll engage in the following activity:

  • Pick the pile that contains the highest number of gifts. If multiple piles share this distinction, you can select any of them.
  • Compute the square root of the number of gifts in the selected pile, and then leave behind that many gifts (rounded down). Take all the other gifts from this pile.
  • You'll do this for "k" seconds. The objective is to find out how many gifts would still remain after these "k" seconds.

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lee

· 2 years ago

Heapq.heapify(some array) is O(n) in python. So the total time complexity is O[n + k * log(n) + n]. I'm not sure what the analysis of largest component here is, so I would just call this O(n + k*log(n)).

For space complexity, because they python heapq library operates on the provided gifts list in place, there is no additional space allocated for a new heap array. Thus the space complexity should be O(1).

Show 2 replies
J

Jimmy

· 2 years ago

Why is the time complexity for the final summation portion O(N)? Shouldn't it be O(N log N) since you are popping all gifts off of the heap to calculate the sum? This seems like an unnecessary step since you don't need a particular ordering of the gifts when calculating the sum - you just need to know how many gifts are remaining.

A more optimized solution would be to get the total number of gifts at the start and deduct the number of gifts taken after each second.

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <numeric>

class Solution {
public:
    int remainingGifts(std::vector<int>& gifts, int k) {
        // ToDo: Write Your Code Here.
        int result = std::accumulate(gifts.begin(), gifts.end(), 0);
        std::priority_queue pq(gifts.be
Show 1 reply
Mykola Zhadanov

Mykola Zhadanov

· 2 years ago

  • Pop an item from the heap, which is O(log(n)).
  • this is incorrect as we always poll Min (or Max), so it's always O(1) operation.
Show 1 reply
csnotebook553

csnotebook553

· 4 months ago

Please update the python version here. Python 3.14+ supports max heap library now, can't use it here