#hmm, could it not be that k can be much
icy garnet
i do like the approach
another way might be to do binary search? maybe one could ask, for each M >= 1, is it possible to achieve a min of at least M after k upgrades? i think this can be done in O(n) time.
largest possible M is at most max(servers). so the search space is [1, max(servers)] and binary search for largest possible M would achieve a runtime of O(n log max(servers)) ?
chilly hedge
nice approach. Im still new to lc didn't know we could solve such problems using binary search over a finite search space
icy garnet
dunno if it is optimal either. someone is suggesting outside this thread that it can be done in O(n) time if input is sorted. hmm well i think we both learned from the methods the other has mentioned, and thats important, even if the runtimes are not so optimal