9. Find the kth Largest Element in an Unsorted Array in Java : FAANG Interviews

In many real-world scenarios, you may need to find the k-th largest element in an unsorted array. A common approach to this problem involves using efficient algorithms and data structures to avoid unnecessary computations, such as sorting the entire array. This problem is often used to assess familiarity with sorting algorithms and efficient searching.

Problem Statement

Given an unsorted array of integers, your task is to find the kth largest element in the array, where k is a positive integer and does not exceed the array size.

Key Concepts

  1. Quickselect Algorithm (O(n) Average Time Complexity)
  2. Heap Data Structures (Min-Heap for kth Largest)
  3. Time Complexity Analysis

Let's examine two of the most commonly used approaches to solving this problem: Quickselect and Heap Data Structures.

1. Quickselect Algorithm

The Quickselect algorithm is an efficient approach based on the well-known Quicksort algorithm. While Quicksort sorts the entire array, Quickselect only partially sorts the array to find the kth largest element, making It faster on average.

How it Works

  1. Choose a Pivot: Like Quicksort, select a pivot element from the array.
  2. Partitioning: Partition the array into two parts — one with elements greater than the pivot and one with elements smaller.
  3. Recursive Search: Depending on the position of the pivot, recursively apply the algorithm to the side where the kth element lies.

Time Complexity

  • Average Case: O(n), where n is the length of the array.
  • Worst Case: O(n^2), which occurs when the pivot is consistently chosen as the smallest or largest element (though this can be mitigated with strategies like random pivot selection).

Java Implementation

import java.util.Random;

public class KthLargestQuickselect {

    // Partition the array
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] >= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Swap two elements in the array
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Quickselect function
    public static int quickSelect(int[] arr, int low, int high, int k) {
        if (low <= high) {
            int pivotIndex = partition(arr, low, high);

            if (pivotIndex == k - 1) {
                return arr[pivotIndex];
            } else if (pivotIndex > k - 1) {
                return quickSelect(arr, low, pivotIndex - 1, k);
            } else {
                return quickSelect(arr, pivotIndex + 1, high, k);
            }
        }
        return -1;
    }

    // Main function to test Quickselect
    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 4; // kth largest element

        System.out.println(k + "th largest element is: " + quickSelect(arr, 0, arr.length - 1, k));
    }
}

In the example above, the Quickselect algorithm is used to find the 4th largest element in the array {7, 10, 4, 3, 20, 15}.

2. Heap Data Structures (Min-Heap for kth Largest)

A Min-Heap is a binary tree data structure in which the parent node is smaller than its children. This property is useful when we need to keep track of the top k largest elements in an array. By maintaining a min-heap of size k, the root of the heap will always be the smallest element in the heap, representing the kth largest element in the entire array array.

How it Works

  1. Build a Min-Heap of Size k: Insert the first k elements from the array into a min-heap.
  2. Iterate through the Rest of the Array: For each remaining element, if it is larger than the root of the heap (which is the smallest element in the heap), replace the root with the new element and reheapify.
  3. Return the Root: After processing all elements, the root of the heap will be the kth largest element.

Time Complexity

  • Building the Heap: O(k)
  • Inserting Elements: O((n - k) * log k)
  • Total Time Complexity: O(n * log k)

Java Implementation

import java.util.PriorityQueue;

public class KthLargestHeap {

    // Function to find the kth largest element
    public static int findKthLargest(int[] nums, int k) {
        // Min-Heap to store k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        // Build the heap
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek(); // The root of the heap is the kth largest element
    }

    // Main function to test Heap approach
    public static void main(String[] args) {
        int[] nums = {7, 10, 4, 3, 20, 15};
        int k = 4; // kth largest element

        System.out.println(k + "th largest element is: " + findKthLargest(nums, k));
    }
}

In this example, we use a Min-Heap to find the 4th largest element in the array {7, 10, 4, 3, 20, 15}.

Summary

Both the Quickselect algorithm and Min-Heap data structure are effective ways to solve the problem of finding the kth largest element in an unsorted array.

  • Quickselect is an average-case O(n) solution that provides a more optimal approach regarding time complexity.
  • Min-Heap provides an O(n * log k) solution and is generally easier to implement, especially when you need to repeatedly retrieve the kth largest element.

The choice of algorithm depends on the problem constraints and whether you prefer a more straightforward approach or are willing to explore more advanced algorithms, such as Quickselect.

Please stay tuned. I will update Point 5 of the FANNG Interview series. The top 10 interview questions are listed here.

0 comments:

Post a Comment