Programming Optimization #1: Maximum Element in Array after Removal of Random Element

Setup

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.

Thinking Process

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!

--

--

--

Writing to soothe the soul, programming to achieve flow

Love podcasts or audiobooks? Learn on the go with our new app.

How to Connect MongoDB container running inside the AWS EC2 instance from MongoDB Compass…

Amazon CloudWatch (Part 2)

Dockerizing a Go App — and Optimising Its Image Size

What the Scrum Masters are Doing all Day? [SURVEY RESULTS]

Merging of Git Branches Using Jenkins Job

15Days15Games — Learn Game Development by Building Games!

Why using Microservices Architecture?

How to be a top 1% developer?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Mipsmonsta

Mipsmonsta

Writing to soothe the soul, programming to achieve flow

More from Medium

LeetCode Patterns Adventure 27 — Lowest Common Ancestor of a Binary Search Tree

Understanding C++ pointers in an array using [], * and & with a code example

Leetcode — Custom Sort String