Finding Nth Largest Term In Unsorted Array

Given a task of finding nth largest term in an unsorted array by obeying following rules ...

Rules

1. You cannot sort an array
2. You cannot use a single library function (No API calls are allowed)
3. A separate copy of array should not be created

This can be easily implemented using a stack where we will start filling the stack with the smallest element, such that at the end we will get largest term at the top.

Algorithm:

1. accept array elements
2. determine the minimum element from the array
3. insert it into the stack
4. repeat step 2 & 3 until stack contains all elements of array
5. accept nth position from the user, say x
6. return the element which is stored at the x position
7. display the result
8. stop

Psuedo code for finding minimum element in an array

imin <-- 0;

        for ( i <-- 0; i < arr.length; i++) {

            imin <-- i;

            for (j <-- 0; j < arr.length; j++) {

                if( a[j] < a[imin] ){

                    imin <-- j;

                }

            }

        }

where " imin " stores index of the minimum element.

Code

package Kthlargestterm;

import java.util.Scanner;

 //@author Naved Momin(navedmomin10@gmail.com)
 
public class KthLargestTerm {

    static int[] a;
    static Scanner s = new Scanner(System.in);
    static int counter = 0;
    static StackUsingLL stack = new StackUsingLL();
    
    public KthLargestTerm(int size) {
        a = new int[size];
    }
    
    int getMin( ){
        int imin = 0;
        for (int i = 0; i < a.length; i++) {
            imin = i;
            for (int j = 0; j < a.length; j++) {
                if( a[j] < a[imin] ){
                    imin = j;
                }
            }
        }
        int k = a[imin];
        a[imin] = Integer.MAX_VALUE;
        return k;
    }
    
     
     static void getData( ){
        System.out.println( "enter size "); 
        int n = s.nextInt();
        KthLargestTerm kth = new KthLargestTerm(n);
        System.out.println( "enter data ");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        
        int min = kth.getMin();
         int c = 0;
        while ( min != Integer.MAX_VALUE && c < n ) {             
            if(!stack.contains(min))
                stack.insert(min); 
            
            min = kth.getMin();
            c++;
         }
        
        System.out.println( "enter nTh position to view nth largest term ");
        int m = s.nextInt();
         while (m != -1) {     
             if( m >= 0 ) {
                    int item = stack.getItem(m);
                    String str =  (m == 1) ? "st" 
                            : (m==2) ? "nd" 
                            : (m == 3 ) ? "rd"
                            : "th";
                    
                    System.out.println( m + str +  " largest term is " + item );
                }
             System.out.println( "press -1 to exit or press any key to continue...");
             m = s.nextInt();
             if( m != -1 ){
                System.out.println( "enter nTh position to view nth largest term ");
                m = s.nextInt();
                
             }
         }
        
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        getData();
    
    }
}   




class Node{
    int data;
    Node next;
}

public class StackUsingLL {
 
    Node top ;
    static int insertAccount = 1;
    
    public boolean isempty( ){
       if( top == null ){
           return true;
       }else
           return false;
    }
    
    public void insert( int x ){
        Node newrec  = new Node();
        newrec.data = x;
        newrec.next = null;
        
        if( top == null ){
            top = newrec;
        }else{
        newrec.next = top;
        top = newrec;
        }

      insertAccount++;
    }
    
    public int delete( ){
        if( isempty() ){
            System.out.println( "stack empty" );
        return -1;
        }
        else{
            int x = top.data;
            top = top.next;
            return x;
        }
    }
    
    public boolean hasNext( ){
        
        if( top != null ){
            return true;
        }
        else{
            return false;
        }
    }
    
    public boolean contains( int min ){
        boolean val = false;
        Node p = top;
        while ( p != null ) {            
            if( stackTop( ) == min ){
                val = true;
                break;
            }
            else
                val = false;
            p = p.next;
        }
        return val;
    }
    
   public int getItem( int index ){
        if( index <= insertAccount ){
            int i = 1;
            int d = -1;
            Node p = top;
            while (p != null) {            
                if( index == i ){
                    d = p.data;
                    break;
                }
                i++;
                p = p.next;
            }
            return d;
        }else{
            System.err.println( "index was out of range ...");
            return -1;
        }
    }
    
    public int stackTop(){
        return top.data;
    }
    
    public void display( ){
        if( isempty() )
            System.out.println( "stack empty");
        else{
            Node p = top;
            while (p != null) {
                System.out.println( p.data + " ");
                p = p.next;
            }
        }
    }
    
}

Output

In case you want *.jar file then download it from here