• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Finding second highest element in an array

 
Raj Kumar Bindal
Ranch Hand
Posts: 418
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can anybody tell the most efficient way to find second highest element in an array in java?
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34863
369
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you know how to find the highest element? If so, you could use a similar technique to store the two highest values.
 
Raj Kumar Bindal
Ranch Hand
Posts: 418
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I did this by taking two variables namely highest and secondhighest. Initially both of these will be having same value and that will be first element of array. After this, we will compare each value of array with these variables and based on this, the value of these variable will change.

So, afte 1 iteration, we will get some value of secondhighest and that is the one which we need.

I am not sure if there is any better approach than this.

Any suggestions.
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorting the array could help.
 
Gopi Chella
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The below is the another way to find second largest element in array.

 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15451
42
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But sorting is probably not the most efficient way that's possible if you just want to get the second highest value.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pencil and paper. And a large eraser! Write down exactly what steps you are going to follow to find the highest and next-highest elements. As Jesper has implied, it should be possible for a single traversal of the whole array. When you have the steps, break them in to smaller steps. Eventually your steps will be small enough to be converted to code easily.
 
Gopi Chella
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Without using Arrays.sort

 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Gopi: please don't provide complete solutions--we strive to teach people how to learn here, which is best done by working through the problems, getting some hints or pointers when necessary, and so on. Handing someone a solution may work short-term, but we're after something deeper, and more meaningful. Thanks.
 
Gopi Chella
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sure Dave. I agree and i am sure this will not happen again.

~Thanks, Gopi
 
Rob Spoor
Sheriff
Pie
Posts: 20611
63
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fortunately that is not the most efficient algorithm. The linear algorithm is of course the fastest, followed by the "sort-and-get".
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David Newton wrote: . . . we strive to teach people how to learn here . . . Thanks.
Thank you for noticing, David and Ernest.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12186
34
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Raj Kumar Bindal wrote:Can anybody tell the most efficient way to find second highest element in an array in java?

"most efficient" in terms of WHAT? Time to code? Memory? Processor usage?

Much of software design requires you to balance various contradictory requirements. Without knowing what is most important to you, we really can't provide an answer.
 
Raj Kumar Bindal
Ranch Hand
Posts: 418
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I will just say better performance by saying that if it has less iterations, less memory utilisation.

I told my way of how i will go ahead to resolve it. But, posted this question to find out if there is any better solution for this.
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Raj Kumar Bindal wrote:I will just say better performance by saying that if it has less iterations, less memory utilisation.

I told my way of how i will go ahead to resolve it. But, posted this question to find out if there is any better solution for this.


Hey i saw this thread this morning and tried to come up with my own solution. I think my solution is pretty long and not as good as it could be and i'm gonna now have a go at a complete rewrite. But if you don't mind i would be interested in seeing your solution to compare, could you post the code please?

This is my solution. I decided to write a whole class called MyArrays with static methods (as i have just learned what they are). So that another class can pass the array as an augument and it will return the second highest.

My solution needs work. I think the problem i had is i saw the way to find the highest element of an array and i got stuck on just constantly adding if else statements to get the results i needed. Instead of completely re thinking it.

Anyway i don't expect this solution to help you as your's is probably already less confusing but i would love to see your solution to compare.

Ok here is the method that needs to be called.


 
fred rosenberger
lowercase baba
Bartender
Posts: 12186
34
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the problem needs to be defined better. Does the array allow duplicates? if not, then your "if (secondHighest == highest)" is not needed.

If duplicates ARE allowed, then you need to define if you want to report duplicates. In other words, if my array contained

{1,2,3,4,5,5}

I think we'd all agree 5 is the highest. But is 5 the second highest, or is 4?

A minor tweak...since you set element [0] as the highest, you can start iterating at i=1.

Or, you could set highest and secondHighest to Integer.min_value and start at element 0...

 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:I think the problem needs to be defined better. Does the array allow duplicates? if not, then your "if (secondHighest == highest)" is not needed.

If duplicates ARE allowed, then you need to define if you want to report duplicates. In other words, if my array contained

{1,2,3,4,5,5}

I think we'd all agree 5 is the highest. But is 5 the second highest, or is 4?

A minor tweak...since you set element [0] as the highest, you can start iterating at i=1.

Or, you could set highest and secondHighest to Integer.min_value and start at element 0...



Hello. The (secondHighest == highest) is there for an important reason. If you were to run the program without that line of code, and the array you were testing had the highest number as the first index in the array, then the code would no longer work because the second highest would have been assigned the highest number with no way for that to change.

going to play about with your suggestions now though. Thanks.

 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(I deleted this message cause i had made an error)
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok so i've now re wrote it so the for loop doesn't go through the first index unnecessarily. But i still stand by what i said about that final else if statement. It just looks like it would be pointless but it's deceiving. I was having major problems when the first index was the highest number in the array and that solved it.



 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:

If duplicates ARE allowed, then you need to define if you want to report duplicates. In other words, if my array contained

{1,2,3,4,5,5}

I think we'd all agree 5 is the highest. But is 5 the second highest, or is 4?





And i'm glad you mentioned that because i wasn't sure what i should do in that case. But the way the code stands it would say that 4 was the second highest.
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ahh damn it. I've just realized my code doesn't always work. It has a flaw.

You know this code would be really easy if i set the initial values of highest and secondHighest to just 0. That was easy to work out. But then i realized that if people wanted to use minus numbers in their array the code didn't work. So i set those varaibles to equal the first index in the array which caused a load of problems. One of them being if the first index was highest then the second highest would actually be assigned the highest number.

Then i thought well another solution would be to just start off by assigning the highest and secondHighest as the lowest possible number for an integer. And that did work but i thought that would be considered messy. Also if the array someone sent only had one index then it would say the second highest number would be -2147483648. So i then added an if statement that said if the array.Length was == 1 then it would just return the first index of the array.

That worked well but i couldn't help thinking it was messy.

Then i came up with that final if else statement which ended the problem when the first index was the highest. But i've just now noticed it messes up in different situations.

I really wasn't expecting this to be so tricky. It's been fun though.

sorry for posting in this thread so many times!
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In that array, there is no second highest. There are top equal and 3rd. I would stick with what you have written which (I think) gives 5 as highest and 4 as next-highest, but that is a personal opinion rather than a definite ruling

And you have identified a problem, and (probably) hit on the correct solution ( ), viz initialise the values to Integer.MIN_VALUE.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nothing wrong with repeated posts; your musings allow others to see how you identify and solve problems.
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Nothing wrong with repeated posts; your musings allow others to see how you identify and solve problems.


Good! Cause here is another one! I THINK i've done it.





So here i have set highest to array[0] and secondHighest to array[1]. I had avoided doing that because i thought it would cause problems if the second highest index was first as I was thinking secondHighest would never get the chance to be assigned to
it, but now reading my own code more carefully i see it does.

Edit i've just realised the lines i had commented out have been left in. I shall just delete them now.
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:In that array, there is no second highest. There are top equal and 3rd. I would stick with what you have written which (I think) gives 5 as highest and 4 as next-highest, but that is a personal opinion rather than a definite ruling

And you have identified a problem, and (probably) hit on the correct solution ( ), viz initialise the values to Integer.MIN_VALUE.


Cool thanks. I hadn't seen this before my last post. I'm going to check out Integer.MIN_Value now. I hadn't heard of that before and i just wanted to see if i could solve the problem with the java vocabulary i had so far.

I think my last post sovled the problem. The one before had a major error if the arrays numbers were in a certain order.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If at all possible use those named variables rather than writing -2146483647; if you make a mistake copying the text you will get a compiler error rather than possible wrong results where you can't see the error.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I previously wrote: . . . can't see the error.
I presume you found my error soon enough.
 
Neil Cartmell
Ranch Hand
Posts: 150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:If at all possible use those named variables rather than writing -2146483647; if you make a mistake copying the text you will get a compiler error rather than possible wrong results where you can't see the error.


I will do thanks. I'm glad i managed to solve the problem without needing the lowest Integer but now I know about that final variable in the Integer class that seems like the tidiest solution.
Thanks again.
 
Edwin Keeton
Ranch Hand
Posts: 214
IntelliJ IDE Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I missed the part where the elements of the array were integers.
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:..."most efficient" in terms of WHAT? Time to code? Memory? Processor usage?

Much of software design requires you to balance various contradictory requirements...

Exactly. Whenever I hear "most efficient," I sigh and think, "I wonder that that means." (When users ask for this, they usually just mean "fast.")
 
Campbell Ritchie
Sheriff
Pie
Posts: 49832
69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I earlier wrote: . . . writing -2146483647 . . .
Did you find the error? It should read -2147483648. (I think)
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic