Extended the solution to determine the nth largest element in an array.

The most efficient methods to find the nth largest element in an array are Quickselect (average O(n) time) and using a min-heap (O(n log k) time, where k is n). A full sort (O(n log n)) is also an option, though often less optimal.

Quickselect (Average O(n))

Quickselect is a selection algorithm that leverages the partitioning logic of Quicksort. It selects a pivot, partitions the array such that elements smaller than the pivot are on one side and larger on the other. Instead of recursing on both sides like Quicksort, it only recurses on the side that contains the nth largest element, significantly reducing the average time complexity. Its worst-case is O(n^2), but this is rare with good pivot selection strategies.

Heap-based Approach (O(n log k))

Using a min-heap of size k (where k is n for the nth largest element), iterate through the array. If the current element is larger than the heap's smallest element (root), remove the root and insert the current element. After processing all elements, the heap's root is the nth largest element. This approach is O(N log k) where N is the total elements and k is the heap size. If k is close to N, it's effectively O(N log N).

import heapq
def find_nth_largest_heap(arr, n):
    # Use a min-heap of size n
    min_heap = []
    for x in arr:
        if len(min_heap) < n:
            heapq.heappush(min_heap, x)
        elif x > min_heap[0]:
            heapq.heapreplace(min_heap, x) # Pop smallest, push new
    return min_heap[0] if min_heap else None

Sorting (O(n log n))

The simplest method is to sort the entire array in descending order and then pick the element at index n-1. While straightforward, it performs unnecessary work by fully ordering all elements when only one specific rank is needed.

The choice of method depends on n and the dataset size. For very large datasets in distributed systems like Spark, a full sort (e.g., df.sort()) can be very expensive due to shuffles across partitions. Quickselect-like algorithms are harder to parallelize efficiently across partitions without significant global coordination. Heap-based approaches can be adapted: each partition finds its top k elements, then these k*num_partitions elements are collected and processed by a single reducer to find the global nth largest. This minimizes shuffle data. If n is small relative to the array size, the heap approach (O(N log k)) is often preferred over a full sort.

In the interview, also mention edge cases like duplicate elements, empty arrays, or n being out of bounds (e.g., n > len(arr)).