You are viewing a single comment's thread. Return to all comments →
The way to do it in O(n) time is to take advantage of the fact that the right and left sides will always contain all the elements except for the current one. So when looping left to right, if one sets the right to contain the sum of all the elements in the array save the first (depends on your implementation), and the left to start off as zero, they can go through the entire array adding the previous element to the left and subtracting the current element from the right then comparing. It becomes a matter of a very simple loop that contains two add/subtract operations and the comparison, and it will only loop over the array one time.
Thank you, that did it! A lot of these challenges require mathematical trickery/shortcuts. "Brute force" coding won't work for a lot of them. The result is that many of these challenges measure mathematical ability more than they measure coding ability.
Well, after all this problem is in the Algorithms section. Finding out a way to reduce time complexity is all about skillfulness in algorithmic programming.
Mind you, if it really were only mathematical trickery such as knowing some obscure theorem in number theory, then I would agree with you. But this rather is algorithmic trickery which is to be expected with algorithmic exercises.
Subtracting from what exactly? What can you subtract from if you don't know the rest of the array? O(n) means that you are able to solve this while reading the numbers in. If you read the array first and then work on top of it it's not O(n).
Yeah you would have to read the numbers into the array first, and yeah that could definitely potentially mean going through the entire array twice, or one and a half times, etc. But it should be noted here that this is still considered a linear rate of growth, and thus stated generally to be O(n). The fact that it could potentially be 2n does not matter much in the long run, what's important is that it's linear. That's how big O notation is typically used and it is to give a general idea of the eventual rate of growth.
I understand and agree... I was just confused by everyone talking about having solved it in a single pass.
From my point of view it is not even O(2n). We should take in count complexity of solving algorithm, not complexity of preparing input data.
It's O(2n) because you have to have the sum before you can look for the pivot, and worse case this takes two full traversals of the array, minus the first and last elements, but if the array is very large leaving those two elements out makes little difference to the worst-case time. So in the limit where n goes to infinity and the inputs are stacked against you, it takes 2n steps through the array to find the answer.
And that's only if you combine the summing with the inputting. If you do all the inputting and then do the summing and then do the searching, it's O(3n).
Big O notation ignores the constant factor. Whether your code goes through the array once, twice or even a hundred times, it is still O(n), as long as the number doesn't increase as n increases.
so can you please tell me how to reduce it ? i mean the complexity? because i am not able to clear 1 test case.
Do you have trouble with test case that is posted for this task? If so I posted above implementation that passed all tests for this task.
what about this testcase
1 7 5 1 4 13 1..
Thank you very much. I was going for O(n^2) after trying more I reached O(n^2/2) or something.
After reading your comment I realized I was still doing lots of unnecessary calculations.