Programming Optimization #1: Maximum Element in Array after Removal of Random Element
Suppose you have an Array A = [10,3,4,5,8,9], what is the fastest way to compute the maximum element in one pass after a random element is removed.
If you are a coder, finding the maximum element is trivial and can be done in one pass by scanning elements one by one and compare the current element to the last largest element encountered. If the current is larger, it is the maximum element for now.
However, the question says that one of the element in the array will be randomly removed. The usual mode of thinking is to wait till the random element is removed, then to find the maximum element by scanning the remaining elements. This means that you will have to repeat the scanning whenever a different element is randomly removed. So if we repeatedly reset and remove a different random element from the array each time, say over a 1000 times, we have to repeat the scanning code for the maximum element for a 1000 times. Obviously this is not the most efficient.
The holy grail is to find the maximum element in one pass — we want to be able to scan the elements in one pass and no matter the number of resets and different element being removed in each reset, we can produce the answer, all without running the “find maximum element code” again.
Here we go
The trick here is to store the second maximum element encountered, in addition to the maximum element as we go through every single element of the array in the single pass.
Then whenever an element is removed, we check whether this removed element is the found maximum element or the found second maximum element. If it is the maximum element, return the second maximum element found previously. If removed element is the same as the second maximum element, return the the maximum element found. If neither, return the maximum element found.
Problem solved. I will not go into the code, but should leave it as an exercise for you.
Happy coding. Do clap if this helped you in your coding journey!