Most Beautiful Item for Each Query - Leetcode 2070 - Python

[@treelibrarian7618]

Just a comment on why to not bother with the leetcode runtimes: they do not provide valid comparison to other coders submissions, for 2 reasons: 1: the runtimes are inconsistent with the exact same code: submit 10 times and see what I mean. variation of 30% to 50% is common, I presume because of a noisy runtime environment. 2: it is possible for users to add testcases to the workload *after* having got their runtime acknowledged. This puts everyone who comes after them at a disadvantage. I have several times tried the code of the "fastest" example (that you can get by clicking on the leftmost bar of the graph), copy paste it into my code window and try it, and it is not only slower than mine but consistently only an average result. I'm up for competition as much as the next man, but the playing field needs to be level.

[@_theone_99]

I only sorted the items array by price (not the queries), and then ran a binary search for each query. Before that, one additional step was, I looped over items and set items[i][1] = max(items[i][1], items[i-1][1]), because if my binary search landed on any index, the answer to that query will be the maximum beauty of all items on or before that, so I just set the max beauty upto index i as the beauty of item[i]. That amounts to nlogn + n + mlogn, beat 100% in time and space, because I reused the queries array as the answer array

[@hamirmahal]

What language? I had a similar approach in JavaScript that only beat 50%.

[@_theone_99]

@@hamirmahal I am using go

[@_theone_99]

@@hamirmahal i used go

[@DeathSugar]

Leetcode runtimes are good way to understand how to optimize your code, so if you want to write performant code than you can try optimize your runtimes. Doesn't really work much for python and other scripting languages, but for compile-time is a bliss - when your solution comes from 2 seconds to 0 ms is a beautiful feeling

[@business_central]

This problem when I was solving it reminded me of one about intervals and queries, it's in the NC 150 - that helped a lot in solving it! Thank you!

[@adityarao4157]

It was a nice problem to learn how exactly lower_bound and upper_bound works (for C++ users ifk)

[@moralized]

Ouch.. I found the brute force solution but didn’t come up with that optimization. Great video as always!

[@BIBIN63]

My intuition was to use hashmaps. I haven’t coded up this yet. 1. Create a hashmap for the items array. Only update the value of a key if the beauty is larger. 2. Create a new array for result, Iterate through the queries and use each as query as a key for the hashmap and insert the value into result array.

[@Tommy-sm4ed]

class Solution: def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]: res = [] beauty_map ={} largest = 0 max_index = 0 items.sort() for p, b in items: largest = max(largest, b) max_index = max(max_index, p) beauty_map[p] = largest for q in queries: temp = min(max_index, q) while temp not in beauty_map and temp > 0: temp -= 1 if temp in beauty_map: res.append(beauty_map[temp]) else: res.append(0) return res

[@lucacorsetti2131]

yes same!

[@tp_pm]

I did the same and got TLE :/

[@nirmalgurjar8181]

instead of hashmap using treemap would be optimal and checking if value less than equal to key exists.

[@waleeddaud3497]

Applied upper bound on items array for each query

[@monismomin6759]

such a good intuitive solution

[@yang5843]

My constant time solution seems to be slower than my binary search solution, which is weird

[@Reck1025]

I did not think to sort the queries array at all 🤯 Is this faster than sorting the the items array and then using binary search?

[@vayunjain9289]

only while queries length is less than items length

[@tp_pm]

sorting the the items array and then using binary search - I did this and got TLE

[@Lamport14]

Thanks

[@challengemania4447]

Java run time is 78 ms and its faster than only 7.25% of java online submission.. But here it is 178 ms and faster than 59%.. Why this ?

[@rahulsiddhardh3701]

It is specific to the language you are using. If you CPP you'll get much lesser times

[@devmahad]

thanks :)

[@ajitpalsingh606]

I only forgot indexes part in queries and rest i was able to do...

[@ZeroTrunks]

I know what amoritiz..... something is...

[@bhanunani1307]

how you come up with these solutions

[@business_central]

First! I've never been here so early lol

[@mosestrosin]

olny items sorted, beats 99% of solutions def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]: items.sort() prices = [] max_beauties = [] current_max = 0 for price, beauty in items: if beauty > current_max: current_max = beauty prices.append(price) max_beauties.append(current_max) results = [] for q in queries: idx = bisect_right(prices, q) - 1 if idx >= 0: results.append(max_beauties[idx]) else: results.append(0) return results