Find nth max last element from unsorted array

We have to find out the nth last max element from the unsorted array. We can solve this problem in multiple ways. We will check some of the ways of doing this.

• Sort last n elements from the input array in descendent order. We can use the similar method as selection sort for sorting last n elements. Method ReturnNthLastElementUsingSelection gives code for this approach.  

 

int ReturnNthLastElementUsingSelection( int * array, int nSize, int nThLast) {     if( NULL == array )         return -1 ;        if( nSize < nThLast )         return -1;     int nCurrentMax = -1;     for( int nIterator = 0; nIterator < nThLast; nIterator++)     {         nCurrentMax = array[nIterator];         int nPos = nIterator;         for( int nTemp = nIterator +1; nTemp < nSize; nTemp++ )         {             if( nCurrentMax < array[ nTemp ] )             {                 nCurrentMax = array[ nTemp ];                 nPos = nTemp;             }         }         array[nPos] = array[ nIterator ];         array[nIterator] = nCurrentMax;     }     return nCurrentMax; }

• If we don't want to modify the given array we can solve this problem with some temporary space by creating the Map which will store our n last max elements. Map is used as a searching would be faster in the map for already added max element.

int ReturnNthLastElementWithTempSpace( int * input, int size, int nThLast) {     if ( NULL == input )         return -1;     if( size < nThLast )         return -1;     int nThMax = 0;     std::map<int, bool> MaxElementIndexMap;          for( int nFinder = 0; nFinder < nThLast; nFinder++ )     {         int pos = 0;         nThMax = -1;         for( int nIterator = 0; nIterator < size; nIterator++)         {             if( nThMax < input[nIterator] )             {                 if( MaxElementIndexMap.find(nIterator) == MaxElementIndexMap.end() )                 {                     nThMax = input[nIterator];                     pos = nIterator;                 }             }         }         MaxElementIndexMap.insert( std::map<int, bool>::value_type(pos, true));     }     return nThMax; }