3
\$\begingroup\$

I have written this code to find second largest element in an array of random integers. If it needs to be optimized, then do comment on it. First of all I'm populating all the elements into the list which does not have any repeating value, then sorting, then in list.size()-2 I have second largest element.

This is one way of doing this:

int[] randomIntegers = {1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9};
int max = Integer.MIN_VALUE;
int secMax = Integer.MIN_VALUE;
List<Integer> list = new ArrayList<>();
for(int i:randomIntegers) {
    if(!(list.contains(i))){
        list.add(i);
    }
}
Collections.sort(list);
System.out.println(list.get(list.size()-2));

If you are not allowed to sort that list then you can do the following to find the second-largest element:

int[] randomIntegers = {1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9};
int max = Integer.MIN_VALUE;
int secMax = Integer.MIN_VALUE;
List<Integer> list = new ArrayList<>();
for(int i:randomIntegers) {
    if(!(list.contains(i))){
        list.add(i);
    }
}
for(int i:list) {
    if(max < i) {
        secMax = max;
        max = i;
    }
    else if(secMax < i){
        secMax = i;
    }
}
System.out.println("Second Largest Number is :" + secMax);
\$\endgroup\$
7
\$\begingroup\$

ArrayList is not the right tool. Since ArrayList makes no attempt to arrange its elements, ArrayList.contains(...) is inefficient — it has to examine every previously added element to see whether it is present. Then, at the end, you still have to sort the entire list. If you're adding n numbers, and adding each number takes O(n) time, then your entire solution is O(n2), which is horrible for such a simple problem.

If you want to use a Java Collections data structure, why not use SortedSet instead? The advantages of SortedSet are:

  • It maintains the order of elements as it adds them
  • It automatically deduplicates (TreeSet does it in O(log n) time)
  • You don't have to sort the elements again at the end

Here's a solution (that works in O(n log n) time):

int[] randomIntegers = { 1, 5, 4, 2, 8, 1, 1, 6, 7, 8, 9 };
SortedSet<Integer> set = new TreeSet<Integer>();
for (int i: randomIntegers) {
    set.add(i);
}
// Remove the maximum value; print the largest remaining item
set.remove(set.last());
System.out.println(set.last());

A more efficient and minimalist solution wouldn't use any data structure. You just keep track of the two largest numbers you have encountered as you walk along the input array. See this related question. That approach hardly uses any space and works in O(n) time, which is as good as it gets.

\$\endgroup\$
1
\$\begingroup\$

The code is not complete. What will happen if the array is like this (9 and 8 are interchanged)?

int[] randomIntegers = {1, 5, 4, 2, 8, 1, 1, 6, 7, 9, 8};
\$\endgroup\$
1
\$\begingroup\$

TreeSet/SortedSet and Collections.sort essentially rely on ordering array and then use DS properties to obtain Second Largest / Second Smallest key.

While same can be done using some of the recursive magic while carrying along Satellite data.

Here is what implementation looks like :

nlog(n) implementation.

public class Test {
  public static void main(String...args){
    int arr[] = new int[]{1,2,2,3,3,4,9,5, 100 , 101, 1, 2, 1000, 102, 2,2,2};
    System.out.println(getMax(arr, 0, 16));
  }

  public static Holder getMax(int[] arr, int start, int end){
    if (start == end)
      return new Holder(arr[start], Integer.MIN_VALUE);
    else {
      int mid = ( start + end ) / 2;
      Holder l = getMax(arr, start, mid);
      Holder r = getMax(arr, mid + 1, end);

      if (l.compareTo(r) > 0 )
        return new Holder(l.high(), r.high() > l.low() ? r.high() : l.low());
      else
        return new Holder(r.high(), l.high() > r.low() ? l.high(): r.low());
    }
  }

  static class Holder implements Comparable<Holder> {
    private int low, high;
    public Holder(int r, int l){low = l; high = r;}

    public String toString(){
      return String.format("Max: %d, SecMax: %d", high, low);
    }

    public int compareTo(Holder data){
      if (high == data.high)
        return 0;

      if (high > data.high)
        return 1;
      else
        return -1;
    }

    public int high(){
      return high;
    }
    public int low(){
      return low;
    }
  }

}
\$\endgroup\$
0
\$\begingroup\$

After sorting

int highestElementIndex = list.indexOf(Collections.max(list)); 
System.out.println("Second highest element is : " + list.get(highestElementIndex - 1));

Without sorting I think your code is all right.

\$\endgroup\$
  • 1
    \$\begingroup\$ if you look at my code. i have also use same thing to the sorted list. \$\endgroup\$ – Umair Sep 18 '13 at 13:36
  • \$\begingroup\$ @Umair sorry I didn't look closely. You are doing the same thing. \$\endgroup\$ – Anirban Nag 'tintinmj' Sep 18 '13 at 15:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.