Largest and second largest

Medium

Use the least number of comparisons to get the largest and 2nd largest number in the given integer array. Return the largest number and 2nd largest number.

Assumptions

• The given array is not null and has length of at least 2

Examples

• {2, 1, 5, 4, 3}, the largest number is 5 and 2nd largest number is 4.

Solution: single elimination

Key Insight:

Loser of each match must be kept in case of largest and second largest matching up early.

After each match, keep the winner as well as the loser in the form of an object

public class Solution {
  class Element {
    List<Integer> losers;
    Integer value;

    Element(int value, List<Integer> losers){
      this.value = value;
      this.losers = losers;
    }
  }
  public int[] largestAndSecond(int[] array) {
    //pre process
    Queue<Element> q = new LinkedList<>(); 
    int i = 0;
    int j = 1;
    while (j < array.length){
      int one = array[i];
      int two = array[j];
      List<Integer> losers = new ArrayList<>();
      if (one >= two){
        losers.add(two);
        q.offer(new Element(one, losers));
      } else {
        losers.add(one);
        q.offer(new Element(two, losers));
      }
      
      i += 2;
      j += 2;
    }

    if (i < array.length){
      q.offer(new Element(array[i], new ArrayList<Integer>()));
    }

    while(q.size() > 1){
      Element one = q.poll();
      Element two = q.poll();

      if (one.value >= two.value){
        one.losers.add(two.value);
        q.offer(one);
      } else {
        two.losers.add(one.value);
        q.offer(two);
      }
    }

    Element winner = q.poll();
    int max = Integer.MIN_VALUE;

    Integer value = winner.value;
    List<Integer> losers = winner.losers;//additional space
    for (int k = 0; k < losers.size();k++){
      max = Math.max(max, losers.get(k));
    }
    return new int[]{value, max};
  }
}

Comparison: O(N + logN)

SC: