Efficient method to find the second largest even int in an array

Question

The assignment is to create a method that finds the second largest even int in an array of ints. I am restricted from using any methods from any libraries.

Here is my code that works for all cases:

public static int getSecondLargestEven(int[] ary) {


int i;

    aryLength = ary.length;
    int largestEven = -1;
    int secondLargestEven = -1;

    for (i = 0; i < aryLength; i++) {
        if (ary[i] % 2 == 0) {
            if (ary[i] > largestEven) {
                if (largestEven != -1)
                    secondLargestEven = largestEven;

                largestEven = ary[i];
            } else { 
                if (ary[i] != largestEven) {
                    if (secondLargestEven == -1 || ary[i] >= secondLargestEven) {
                        secondLargestEven = ary[i];
                    }
                }
            }
        }
    }

Prior to calling the methodI require the array to have more than one even else no method call. So, when secondLargestEven == -1, I know there is a duplicate.

Is there a more efficient (less use of operators, less loops used, less memory allocation) way to accomplish the objective? How can I improve the logic of my code? How can I improve my code overall? I don't like that I have to assign the magic number -1 to secondLargestEven and largestEven because they are technically named to hold EVENS. Would it be efficient to use a loop to assign a valid even integer in the array to both secondLargestEven and largestEven and THEN proceed to search? Thanks in advance.

For working code that you would like to improve (runtime, resources or general style/architecture), you'd be best served at [CodeReview.SE](http://codereview.stackexchange.com/) — Ordous, Sep 26 '14 at 17:09
Your code seems to be efficient, in terms of performances, even if it isn't nice. Code elegance and best efficiency are often incompatible — Joel, Sep 26 '14 at 17:10
@Joel I would argue that asymptotic efficiency is very compatible with elegance in most cases. Now making something use 1 byte less may make ugly code. — Ordous, Sep 26 '14 at 17:12
This question appears to be off-topic because questions about Best practices and Performance belong to http://codereview.stackexchange.com/ — bummi, Sep 26 '14 at 17:49

Chris Taylor · Answer 1 · 2014-10-06T07:42:52.270

You can make the code cleaner by not explicitly checking for the case when the largest and second variables are equal to -1.

Just set these variables to Integer.MIN_VALUE before the loop - this is the same as assuming that there were two additional values in your array that come before all the others, and they both have the value Integer.MIN_VALUE.

public static int secondLargestEven(int[] x) {

    int largest = Integer.MIN_VALUE;
    int second = Integer.MIN_VALUE;

    for (int i = 0; i < x.length; i++) {
        if (x[i] % 2 == 0) {
            if (x[i] > largest) {
                second = largest;
                largest = x[i];
            } else if (x[i] > second) {
                second = x[i];
            }
        }
    }

    return second;

}

Edit -- I thought I'd throw in that you can remove one level of nesting by using a continue statement inside the loop to skip the cases where you have an odd integer, although some people would consider this more difficult to understand than the code above.

It's a tradeoff - you use explicit control flow inside the loop (bad) but you remove a nesting level (good).

public static int secondLargestEven(int[] x) {

    int largest = Integer.MIN_VALUE;
    int second = Integer.MIN_VALUE;

    for (int i = 0; i < x.length; i++) {
        if (x[i] % 2 != 0) 
            continue;
        if (x[i] > largest) {
            second = largest;
            largest = x[i];
        } else if (x[i] > second)
            second = x[i];
        }
    }

    return second;

}

Just a fun thought... in Haskell, this function can be written in one line

import Data.List (sort)

secondLargestEven = (!! 1) . reverse . sort . filter even

or, if you want to be more efficient

import Data.List (sortBy)
import Data.Ord  (comparing)

secondLargestEven = (!! 1) . sortBy (comparing negate) . filter even

You can replace `Integer.MIN_VALUE` with `-2147483648` if you like, but in my opinion it makes the code less clear :) — Chris Taylor, Sep 26 '14 at 17:08
Quick question: Is it more efficient to assign x.length to some variable of type int so I won't call .length() every time the loop iterates? — qnob, Sep 26 '14 at 17:11
No, because `length` is a special attribute of the array, not a method, so you won't incur method call overhead. See this answer - http://stackoverflow.com/questions/9297899/arrays-length-property — Chris Taylor, Sep 26 '14 at 17:13

przemek hertel · Answer 2 · 2014-09-26T18:10:44.570

This is just-for-fun implementation:

public static int secondLargestEven(int[] array) {

    Set<Integer> evenSet = new TreeSet<>(Collections.reverseOrder());
    for (int n : array) if (n % 2 == 0) evenSet.add(n);
    return new ArrayList<>(evenSet).get(1);
}

This method is extremely inefficient (I cant look at it) but returns second largest even number :)

Method works only if array has second largest even number.

Efficient method to find the second largest even int in an array

2 Answers2