# Find the third largest element in the array in linear time

Find Third largest element in an array

Input : arr[] = {1, 14, 2, 16, 10, 20}

Output : 14

Its a simple program, but would be great to know how it can be improved for better readability or any feedback regarding styling, etc.

public static int findThirdLargest(int[] numbers) {
if (numbers.length < 3) {
throw new IllegalArgumentException("there should be at least three numbers");
}

int largest, secondLargest, thirdLargest;
largest = secondLargest = thirdLargest = Integer.MIN_VALUE;

for (int number : numbers) {

if (number > largest) {
thirdLargest = secondLargest;
secondLargest = largest;
largest = number;
} else if (number > secondLargest) {
thirdLargest = secondLargest;
secondLargest = number;
} else if (number > thirdLargest) {
thirdLargest = number;
}
}

return thirdLargest;
}

@Test
public void findThirdLargest() throws Exception {

// with positive numbers
Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3}));
Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3, 4}));
Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 4, 3, 2}));
Assert.assertEquals(14, ThirdLargestNumber.findThirdLargest(new int[]{1, 14, 2, 16, 10, 20}));
Assert.assertEquals(16, ThirdLargestNumber.findThirdLargest(new int[]{19, -10, 20, 14, 2, 16, 10}));

// with negative numbers
Assert.assertEquals(-100, ThirdLargestNumber.findThirdLargest(new int[]{-100, -2, -3}));
Assert.assertEquals(-3, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, -3, -1000}));
Assert.assertEquals(-3000, ThirdLargestNumber.findThirdLargest(new int[]{-1000, -2000, -3000, -4000, -5000}));

// what happens when all the numbers are same
Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 1, 1, 1}));
}

• Please clarify how ties are supposed to be treated. – 200_success Apr 6 '18 at 19:02

I think overall it is well done, it is clear and readable. Some general tips:

• You can make the parameter a varargs, which makes it easier to call:

public static int findThirdLargest(int... numbers)
...
int thirdLargest = findThirdLargest(1, 2, 3);

• Since you check for the size of the array, you could perhaps also check if it is not null.

• This is somewhat personal, but I would always declare and initialise each variable on a separate line, e.g.:

int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
int thirdLargest= Integer.MIN_VALUE;


To me it helps readability and potentially refactoring later on.

• I'd remove the newline after the for loop opener. It decreases readability for me.

Nice that you added tests! You covered some good cases. You could take a look at Hamcrest matchers, you can create some nice declarative tests with it. They can also show quite decent messages in case a test fails.

Some extra tips about the current tests:

• I'd split up the tests in a couple of different methods
• Personally, I like to use static imports, so you can write:

assertEquals(1, findThirdLargest(1, 2, 3))

• Also do not forget to test for failing cases. Test that when you pass less than 3 numbers, you expect an exception.

And what should the output of findThirdLargest(1, 1, 2, 2, 3, 3) be?

Lastly, a follow up exercise: how would you implement it if the user wants to find the k-th largest element?