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.
Yes, and don't be fooled by thinking that an algorithm that iterates only once over the items is necessarily faster than one that iterates over them multiple times.
The number of operations per iteration plays an important role, so an algorithm that iterates once, but with many operations, can be slower than an algorithm that iterates multiple times with very few operations per iteration, because the latter algorithm may perform fewer total operations.
As a case in point, here is a close Kotlin equivalent of the Python code at the top of this thread:
The code above iterates over the array 3 times: once each for sum, max, and min.
Here's another solution that iterates over the array only once, collecting the running sum, min, and max simultaneously along the way. Yes, you might argue it's a bit contrived, but it's not a totally unreasonable solution, as it proves my point.
The overhead of this approach (1 iteration) causes it to take nearly 10 times longer than the preceding solution (3 iterations). Of course, the timings I took were very rough, and if the array were longer, the overhead of the latter solution might be less significant, but in any case, the latter solution (1 iteration) is clearly and significantly less performant than the former solution (3 iterations).
Here is another solution that iterates over the array only once, but is indeed faster than the first solution (3 iterations) above, by approximately 50% for 5 items (YMMV):
The code is longer than the first solution, and is arguably less readable. It certainly (arguably?) imposes a bit more cognitive load to comprehend than the first solution does. In this case, it could be argued that the first solution is more desirable. In other words, at some point, the difference in performance might not be large enough to give up the arguably clearer solution. Ease of understanding might simply trump performance.
There's one more thing to consider here as well. Because of the simplicity (and clarity) of the first solution, the likelihood of bugs is greatly reduced due to the use of built-in functionality that precludes the need for explicit looping, as given in the third solution. When you use explicit looping, you introduce the chance for one-off bugs, and the like.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Mini-Max Sum
You are viewing a single comment's thread. Return to all comments →
Yes, and don't be fooled by thinking that an algorithm that iterates only once over the items is necessarily faster than one that iterates over them multiple times.
The number of operations per iteration plays an important role, so an algorithm that iterates once, but with many operations, can be slower than an algorithm that iterates multiple times with very few operations per iteration, because the latter algorithm may perform fewer total operations.
As a case in point, here is a close Kotlin equivalent of the Python code at the top of this thread:
The code above iterates over the array 3 times: once each for
sum
,max
, andmin
.Here's another solution that iterates over the array only once, collecting the running sum, min, and max simultaneously along the way. Yes, you might argue it's a bit contrived, but it's not a totally unreasonable solution, as it proves my point.
The overhead of this approach (1 iteration) causes it to take nearly 10 times longer than the preceding solution (3 iterations). Of course, the timings I took were very rough, and if the array were longer, the overhead of the latter solution might be less significant, but in any case, the latter solution (1 iteration) is clearly and significantly less performant than the former solution (3 iterations).
Here is another solution that iterates over the array only once, but is indeed faster than the first solution (3 iterations) above, by approximately 50% for 5 items (YMMV):
The code is longer than the first solution, and is arguably less readable. It certainly (arguably?) imposes a bit more cognitive load to comprehend than the first solution does. In this case, it could be argued that the first solution is more desirable. In other words, at some point, the difference in performance might not be large enough to give up the arguably clearer solution. Ease of understanding might simply trump performance.
There's one more thing to consider here as well. Because of the simplicity (and clarity) of the first solution, the likelihood of bugs is greatly reduced due to the use of built-in functionality that precludes the need for explicit looping, as given in the third solution. When you use explicit looping, you introduce the chance for one-off bugs, and the like.