Timeline for Heaviest Stone algorithm time complexity
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 28, 2021 at 18:15 | review | Close votes | |||
| Sep 29, 2021 at 12:25 | |||||
| Aug 29, 2020 at 10:25 | answer | added | Drew Reese | timeline score: 8 | |
| Aug 11, 2020 at 16:54 | comment | added | slepic | I know but js does not have those heap functions. I meant it to show you how the stones problem can be solved using heap. But implementing the heap functions in js is up to you. Look them up on wiki, they are usualy called build-heap or heapify, sift-up and sift-down, or sometimes bubble-up and bubble-down. | |
| Aug 11, 2020 at 14:53 | comment | added | myTest532 myTest532 | @slepic I'm looking for a solution in Javascript | |
| Aug 11, 2020 at 4:42 | comment | added | slepic | And use @ and my name in further comments So i get a notification please :) | |
| Aug 11, 2020 at 4:41 | comment | added | slepic | If you dont mind i would like to hear back from you. Did it put you on the right path? After all I implemented the C++ solution just to show it to you... | |
| Aug 9, 2020 at 9:31 | comment | added | slepic | But also it feels like smashing the two heaviest stones every time may already give the smallest possible result. So I would start by trying to logacily prove (or disprove) such statement. | |
| Aug 9, 2020 at 9:29 | comment | added | slepic | I added a C++ solution here: codereview.stackexchange.com/questions/247668/… It's a bit more complex and the crucial parts are implemented by the C++'s standard library, but I'm sure you can find code of the 3 functions on wiki. Map won't help you in any way here. For the followup problem, it looks like NP hard, because you can try all permutations of the input to find the smallest result. | |
| Aug 8, 2020 at 23:34 | comment | added | myTest532 myTest532 | Could you please show me an example of how a priority queue would solve this problem? I could using a Map() in javascript | |
| Aug 8, 2020 at 22:57 | comment | added | Countingstuff | The data structure you want is a priority queue, en.wikipedia.org/wiki/Priority_queue, this essentially solves the problem of having to repeatedly sort the collection. Unfortunately js doesn't come with priority queues built in, the lack of good built in datastructures is an unfortunate fact about the language imo, so you'll have to implement it yourself or use a dependency. | |
| Aug 8, 2020 at 21:21 | comment | added | myTest532 myTest532 | A follow up problem is: "Each turn, we choose any two rocks and smash them together. At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)" Any idea how can I approach this problem in order to have the smallest possible weight | |
| Aug 8, 2020 at 19:46 | comment | added | myTest532 myTest532 | Thank you. Yes, it is what I thought O(n^2log(n)). Could you please show me how could I change it to O(nlog(n)) or O(n) if it's possible. | |
| Aug 8, 2020 at 5:15 | comment | added | slepic | O(n^2 * log(n)) is yours. O(n^2) if you implement what @cliesens proposed. O(n * log(n)) if you are willing to implement heap. | |
| Aug 8, 2020 at 1:38 | comment | added | sɪʒɪhɪŋ βɪstɦa kxɐll | For this case it approximates $$O(n^2\ln(n))$$ (as worst case in general) because you are sorting them in the while loop. | |
| Aug 8, 2020 at 0:03 | comment | added | cliesens | If you're worried about efficiency, couldn't you simply go through the entire list and find the two heaviest stones instead of sorting everytime? You can create a new function for this, and I think it should give you a significant increase in performance. | |
| Aug 8, 2020 at 0:00 | history | tweeted | twitter.com/StackCodeReview/status/1291887045212811265 | ||
| Aug 7, 2020 at 21:19 | history | asked | myTest532 myTest532 | CC BY-SA 4.0 |