We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Your solution's complexity is O(N^2) as you will start from
0th to Nth
1st to 0th
2nd to 1st
3rd to 2nd
...
Nth to N-1th
each step will take N time and there are N step. So the worst case time complexity will be O(N^2). Correct me if I am wrong. I have done this way and I have used loop inside loop and it's time complexity is O(N^2).
I don't think that's the method Gladdyu is proposing. His method would have worst case complexity of O(N), because all you do is go through the loop once, and at each stop record the total amount of gas up to that point, which could be negative if there is a greater amount of distance traveled to that point than gas gained. Then the point with the minimum amount of gas is the answer.
Gladdyu, I think there's one error in what you said though; if there are two global minima, it doesn't matter, because that would just mean that you'd get to the second minima with 0 gas, but gain however much gas is there, so you can keep going.
without any investigation my guess is a mod, persumable because you linked a solution of some sort. They should do a [comment deleted because xyz] not just ninja remove them. Again this speculation.
Truck Tour
You are viewing a single comment's thread. Return to all comments →
Your solution's complexity is O(N^2) as you will start from
0th to Nth
1st to 0th
2nd to 1st
3rd to 2nd
...
Nth to N-1th
each step will take N time and there are N step. So the worst case time complexity will be O(N^2). Correct me if I am wrong. I have done this way and I have used loop inside loop and it's time complexity is O(N^2).
I don't think that's the method Gladdyu is proposing. His method would have worst case complexity of O(N), because all you do is go through the loop once, and at each stop record the total amount of gas up to that point, which could be negative if there is a greater amount of distance traveled to that point than gas gained. Then the point with the minimum amount of gas is the answer.
Gladdyu, I think there's one error in what you said though; if there are two global minima, it doesn't matter, because that would just mean that you'd get to the second minima with 0 gas, but gain however much gas is there, so you can keep going.
Yep, you're correct!
Is there a comment from Gladdyu im missing? He isnt purposing an algorithm anywhere I can see (a required element for their to be an upper bound).
It appears as if some of my comments got deleted by someone...
without any investigation my guess is a mod, persumable because you linked a solution of some sort. They should do a [comment deleted because xyz] not just ninja remove them. Again this speculation.
Thanks for the update.