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.
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.
Sherlock and Array
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.