CODEWITHSUNDEEP
calgorithm
Zarsr
Zarsr

Reputation: 51

Finding Maximum Value in an array

One thousand(1000) elements are entered into an array (no memory constraints). As we know, while entering the elements we can update the max out of entered values by a check whenever we enter a value.

But imagine if the position of max value is somewhere around 900

If I remove 200 elements from positions 800 to 1000, without doing any more comparisons, we should have the next max value. Will that mean while entering the data we should have a plan to organize the data in some way to get the max value out of the remaining data?

Deleting and inserting will keep on happening, but we should have max value updated in less time with less no of steps. (Using stacks might help is the clue that the interviewer gave me). Anyone please help me.

Upvotes: 1

Views: 147

Answers (3)

Amit Sharma
Amit Sharma

Reputation: 2067

You should use max heap data structure. The property of max-heap is that you can get the max value in O(1) time. Whereas each insertion and deletion will take O(log(n)) time. For more info check here

Upvotes: 0

Pavel Gatnar
Pavel Gatnar

Reputation: 4053

Create a tree structure upon the array. In each node keep the range and maximum of the subtree. On removing/inserting update the maximum in affected nodes bottom-up.

Upvotes: 0

Xiaotian Pei
Xiaotian Pei

Reputation: 3260

A maximum heap may work in your case. But since 1000 is really small, you may don't need something complicated.

Upvotes: 1

Related Questions