Finding the second largest element of large input sets

Question

I have a problem where I need to find the second maximum element of the user inputs. It's an online practice problem and I can't figure out why the server responds back with a Non-Zero Exit Code error when I submit my code. The program produces right outputs every single time when tested locally. Can someone tell me which part of my code is prone to such errors and how I can deal with this error?

Sample Input: Sample Output:
2 7
1 3 5 7 8 -1 16
12 23 16 0 2 -1

The first input is the number of test cases. Second and third inputs are the actual user inputs respectively. And user inputs are always terminated with -1.

Here is my code:

class SecondLargest {
 public static void main(String[] args) {
 Scanner sc=new Scanner(System.in);
 int testcase=Integer.parseInt(sc.nextLine());
 while(testcase-->0){
 ArrayList<Long> al=new ArrayList<>();
 long num=0;
 long i=0;
 while((num=(sc.nextLong()))!=-1){
 al.add(num);
 i++;
 }
 Collections.sort(al);
 if(al.size()==0){
 System.err.println("");
 }
 else if(al.size()==1){
 System.out.println(al.get(0));
 }
 else if(al.size()>1){
 System.out.println(al.get((int)(al.size()-2)));
 }
 }
 }
}

Large input sets will be used to test the program.

• 200_success: Could you please add a link to the programming-challenge? Also, state the size constraints — what is the longest line you are expected to handle?
• 200_success: @janos The program works for small inputs.
• arindrajit: There are no size constraints given.

Answer 1

So your code seems to work fine, but you get a non-zero exit code for some unknown inputs... What could go wrong? If I call out to you 100 numbers, do you need to remember all of them to tell me the second highest? (inside an array in your head) You don't. And the program doesn't either. Most probably the program crashes with an out of memory error.

Here's one way to solve this using constant storage:

 while (testcase-- > 0) {
 long num;
 long largest = Long.MIN_VALUE;
 long secondLargest = Long.MIN_VALUE;
 while ((num = sc.nextLong()) != -1) {

if (num> largest) {
secondLargest = largest;
largest = num;
} else if (num> secondLargest) {
secondLargest = num;
}

 }
 System.out.println(secondLargest);
 }

Code review

Your code had serious formatting issues. Cleaned up, your code would look like this:

 while (testcase-- > 0) {
 List<Long> numbers = new ArrayList<>();
 long num;
 while ((num = sc.nextLong()) != -1) {
 numbers.add(num);
 }
 Collections.sort(numbers);
 if (numbers.size() == 0) {
 System.err.println("");
 } else if (numbers.size() == 1) {
 System.out.println(numbers.get(0));
 } else {
 System.out.println(numbers.get(numbers.size() - 2));
 }
 }

What changed?

• Formatting fixed
• Use interface type instead of implementation (List)
• Removed redundant variables
• Removed redundant initializations
• Removed redundant parentheses
• Improved variable names

Answer 2

Complexity

There are several inefficiencies that prevent your program from scaling to handle large inputs.

One issue is that you call Collections.sort(). Sorting a list of n elements takes O(n log n) time.

Another issue is that your ArrayList takes O(n) space to store n numbers. A further complication is that if the ArrayList grows beyond the original capacity, the list needs to internally reallocate its internal array and copy all of its contents to the expanded array.

Think about how you could solve this problem without storing all of the numbers. If you had to find the largest entry, how would you do it? Now try to extend that approach to get the second-largest.

Answer 3

Nitpicks

i is a useless variable.

if (al.size() == 1) is an incorrect special case. A one-element list cannot possibly have a second-largest element.

There's no point in storing Long values if you cast the final display back to an int.

It is conventional to put a space before and after binary operators. For example,

while((num=(sc.nextLong()))!=-1){

should be written as

while ((num = sc.nextLong()) != -1) {

Answer 4

Your overall method of sorting the list would be good if the program called for finding the kth largest number in a list of size n where k and n were unspecified beforehand. However, if we know (or can assume) that k << n then there is a faster method that just requires using more memory.

It's often nice to think of how you would perform the task yourself in problems like this. If you had a stack of papers with number grades and needed to find the second highest grade would you sort all of the papers first or could you use your memory to help you solve the problem faster?