CODEWITHSUNDEEP
java
Pallavi Singh
Pallavi Singh

Reputation: 133

Given an array of integers, find out the third largest value in the array

public int thirdLargest(int[] arr){

        int f_l = arr[0];
       int s_l = arr[0];
        int t_l = arr[0];

        for(int i=1;i<arr.length;i++)
        {
        if (f_l < arr[i]){
        t_l = s_l;
        s_l = f_l;
        f_l = arr[i];
        }
        else if (s_l < arr[i]){
        t_l = s_l;
        s_l = arr[i];
        }
        else if (t_l < arr[i]){
        t_l = arr[i];
        }
        }
    return t_l;
 }

my code didn't passes some cases,any suggestion?

parameter {24,27,30,31,34,37,40,42}' , passes

parameter {2,-1,-2,-3,-4,-5}' , fails

Upvotes: 1

Views: 849

Answers (4)

Arijoon
Arijoon

Reputation: 2300

This was actually an interesting question to me to do in O(n) complexity. I hope this solution is order n. I used an ArrayList as a stack (since Stack object won't allow addition of items in specific incidences (I've generalized it). 

public int thirdLargest(int[] arr){
  public int N_TH = 3; // Assuming this is nth largest you want
  public ArrayList<Integer> largest = new ArrayList<Integer>(N_TH);

  for(int i = 0;i<N_TH;i++)
    largest.add(0); // initialize the ArrayList

  for(int i = 0;i<arr.length;i++) {
    for(int j=0;j<largest.size();j++){
      if(arr[i] >= largest.get(j)) {
        // Add the item at the correct index
        // Pop the last element
        largest.remove(largest.size()-1);
        largest.add(j,arr[i]);
        break;
      }
    }
  }
  return largest.get(N_TH);
}

Let me know if you find any problems with it, I might have mistyped part of trying to put it in OP's method.

EDIT won't work with negative numbers at the moment. You can find the smallest value in arr and initialize largest with that value. Then it'll also with negative numbers

Upvotes: 0

Shawn Mehan
Shawn Mehan

Reputation: 4568

Well, as an alternative to your working code, here is a solution that will allow you to find the Nth largest integer in your array using Collections to do the heavy lifting:

import java.util.Arrays;
import java.util.Collections;

public class ArrayNthLargest {

  public static int getNthLargest(int[] arrayInput, int n) {

      Integer[] sortedArray = new Integer[arrayInput.length];

      for (int i = 0; i < arrayInput.length; i++) {
          sortedArray[i] = new Integer(arrayInput[i]);
      }

      Arrays.sort(sortedArray, Collections.reverseOrder());
      return (sortedArray[n - 1]);
  }

  public static void main(String[] args){
      int nth = new Integer(0);
      int n = new Integer(3);
      int[] testArray = {1,2,3,4,5,6,23,44,55,8,1};

      nth = getNthLargest(testArray, n);
      System.out.printf("The %d sorted array value is %d", n, nth);

  }
}

Upvotes: 0

Dici
Dici

Reputation: 25960

There is actually a well-known algorithm for this, which is more generic than yours. It is called quick-select and looks like a quick sort with an optimization making it faster (linear time in average) : since we don't need to sort the array, we just recurse on the part of the array containing the index we are looking for (in your case, third item so index 2).

Here is an implementation in Java :

private static final Random rd = new Random();

public static int kthElement(int[] arr, int k) {
    return kthElement(arr,k,0,arr.length);
}

private static T kthElement(int[] arr, int k, int min, int max) {
    if (min < max - 1) {
        int p = pivot(arr,min,max);
        return p == k - 1 ? arr[p]                      : 
               p <  k - 1 ? kthElement(arr,k,p + 1,max) : kthElement(arr,k,min,p);
    }
    return arr[min];
}

private static int pivot(int[] arr, int min, int max) {
    int pivot = min + rd.nextInt(max - min);
    swap(arr,pivot,max - 1);
    pivot = min;
    for (int i=min ; i<max ; i++) 
        if (arr[i] < arr[max - 1]) swap(arr,i,pivot++); 
    swap(arr,max - 1,pivot);        
    return pivot;
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i]  = arr[j];
    arr[j]  = tmp;
}

Upvotes: 0

user4668606
user4668606

Reputation:

This is simply cause by the fact that you initialize all values to arr[0]. If all elements are smaller than arr[0] this code won't update the values, even though the second-largest element for example wouldn't be arr[0]. Instead initialize the variables for the third/second/largest value with Integer.MIN_VALUE and start the search with the first element (index = 0) instead of the second.

Upvotes: 5

Related Questions