Find the third largest element in the array in linear time

Question

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}));
}

Code: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/ThirdLargestNumber.java#5

Answer 1

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?