File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Finding second highest element in an array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Finding second highest element in an array" Watch "Finding second highest element in an array" New topic
Author

Finding second highest element in an array

Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
Can anybody tell the most efficient way to find second highest element in an array in java?
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30392
    
150

Do you know how to find the highest element? If so, you could use a similar technique to store the two highest values.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
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

Joined: Nov 24, 2005
Posts: 14687
    
  16

Sorting the array could help.


[My Blog]
All roads lead to JavaRanch
Gopi Chella
Ranch Hand

Joined: Apr 26, 2010
Posts: 53
The below is the another way to find second largest element in array.



SCJP 1.5
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14117
    
  16

But sorting is probably not the most efficient way that's possible if you just want to get the second highest value.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38519
    
  23
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

Joined: Apr 26, 2010
Posts: 53
Without using Arrays.sort

David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

@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

Joined: Apr 26, 2010
Posts: 53
Sure Dave. I agree and i am sure this will not happen again.

~Thanks, Gopi
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19685
    
  20

Fortunately that is not the most efficient algorithm. The linear algorithm is of course the fastest, followed by the "sort-and-get".


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38519
    
  23
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

Joined: Oct 02, 2003
Posts: 11257
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
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

Joined: Feb 13, 2010
Posts: 150
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

Joined: Oct 02, 2003
Posts: 11257
    
  16

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

Joined: Feb 13, 2010
Posts: 150
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

Joined: Feb 13, 2010
Posts: 150
(I deleted this message cause i had made an error)
Neil Cartmell
Ranch Hand

Joined: Feb 13, 2010
Posts: 150
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

Joined: Feb 13, 2010
Posts: 150
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

Joined: Feb 13, 2010
Posts: 150
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

Joined: Oct 13, 2005
Posts: 38519
    
  23
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

Joined: Oct 13, 2005
Posts: 38519
    
  23
Nothing wrong with repeated posts; your musings allow others to see how you identify and solve problems.
Neil Cartmell
Ranch Hand

Joined: Feb 13, 2010
Posts: 150
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

Joined: Feb 13, 2010
Posts: 150
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

Joined: Oct 13, 2005
Posts: 38519
    
  23
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

Joined: Oct 13, 2005
Posts: 38519
    
  23
I previously wrote: . . . can't see the error.
I presume you found my error soon enough.
Neil Cartmell
Ranch Hand

Joined: Feb 13, 2010
Posts: 150
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

Joined: Jul 10, 2002
Posts: 214

I missed the part where the elements of the array were integers.


SCJP, SCWCD
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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.")


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38519
    
  23
I earlier wrote: . . . writing -2146483647 . . .
Did you find the error? It should read -2147483648. (I think)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Finding second highest element in an array