What is the time complexity of Kth Largest Element in an Array?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Kth Largest Element in an Array?

This problem uses Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Kth Largest Element in an Array?

Insight 1: The problem can be solved without fully sorting the array, leading to a more efficient solution than using standard sorting algorithms. Insight 2: Quickselect algorithm provides an efficient way to find the k-th largest element by partitioning the array around a pivot, similar to Quicksort.

Which companies ask LeetCode 215. Kth Largest Element in an Array in interviews?

This problem is frequently asked at AMD, Accenture, Avito, ByteDance, Coupang and 28 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Kth Largest Element in an Array - LeetCode 215 Solution

Q: How to solve Kth Largest Element in an Array?

The provided solution uses the Quickselect algorithm, a variation of Quicksort, to find the k-th largest element without fully sorting the array. The algorithm works by repeatedly partitioning the array around a pivot element. The goal is to place the pivot element in its correct sorted position. After partitioning, if the pivot's index is equal to `n - k` (where `n` is the length of the array), then the pivot element is the k-th largest element, and we return it. If the pivot's index is less than `n - k`, it means the k-th largest element is in the right partition, so we recursively search in the right partition. Otherwise, the k-th largest element is in the left partition, and we search there.

Kth Largest Element in an Array - Complete Solution Guide

Kth Largest Element in an Array is LeetCode problem 215, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer array nums and an integer k , return the k th largest element in the array . Note that it is the k th largest element in the sorted order, not the k th distinct element. Can you solve it without sorting? Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4 Constraints: 1 <= k <= nums.length <= 10 5 -10 4 <= nums[i] <= 10 4

Detailed Explanation

The problem asks us to find the k-th largest element in an unsorted integer array. Importantly, it's the k-th largest element in the *sorted* order, not the k-th *distinct* element. For example, in `[3, 2, 1, 5, 6, 4]` if `k=2`, the sorted array is `[1, 2, 3, 4, 5, 6]`, and the 2nd largest element is 5. The constraints state that `1 <= k <= nums.length <= 10^5` and `-10^4 <= nums[i] <= 10^4`.

Solution Approach

The provided solution uses the Quickselect algorithm, a variation of Quicksort, to find the k-th largest element without fully sorting the array. The algorithm works by repeatedly partitioning the array around a pivot element. The goal is to place the pivot element in its correct sorted position. After partitioning, if the pivot's index is equal to `n - k` (where `n` is the length of the array), then the pivot element is the k-th largest element, and we return it. If the pivot's index is less than `n - k`, it means the k-th largest element is in the right partition, so we recursively search in the right partition. Otherwise, the k-th largest element is in the left partition, and we search there.

Step-by-Step Algorithm

Step 1: Calculate the target index: `target_index = n - k`, where `n` is the length of the input array `nums`. This index represents the position of the k-th largest element in the sorted array.
Step 2: Initialize `left` and `right` pointers to the start and end of the array, respectively. These pointers define the search space within the array.
Step 3: While `left` is less than or equal to `right`, perform the following steps (the core Quickselect logic):
Step 4: Choose a random pivot index `pivot_idx` within the current search space (`left` to `right`). This helps to avoid worst-case scenarios for skewed arrays.
Step 5: Move the pivot element to the end of the current search space by swapping `nums[pivot_idx]` and `nums[right]`.
Step 6: Initialize `store_idx` to `left`. This index will keep track of the boundary between elements smaller than the pivot and elements greater than or equal to the pivot.
Step 7: Iterate through the current search space from `left` to `right - 1`. For each element `nums[i]`, if it's less than the `pivot_val`, swap it with the element at `nums[store_idx]` and increment `store_idx`.
Step 8: After the loop, swap the pivot element (currently at `nums[right]`) with the element at `nums[store_idx]`. This places the pivot element in its final sorted position within the current search space.
Step 9: Check if `store_idx` is equal to `target_index`. If so, the k-th largest element is `nums[store_idx]`, and we return it.
Step 10: If `store_idx` is less than `target_index`, the k-th largest element is in the right partition, so update `left = store_idx + 1` and continue the loop.
Step 11: If `store_idx` is greater than `target_index`, the k-th largest element is in the left partition, so update `right = store_idx - 1` and continue the loop.

Key Insights

Insight 1: The problem can be solved without fully sorting the array, leading to a more efficient solution than using standard sorting algorithms.
Insight 2: Quickselect algorithm provides an efficient way to find the k-th largest element by partitioning the array around a pivot, similar to Quicksort.
Insight 3: Randomly choosing the pivot helps to avoid worst-case time complexity scenarios, especially for potentially skewed input arrays.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect.

Companies

Asked at: AMD, Accenture, Avito, ByteDance, Coupang, Deloitte, Deutsche Bank, EPAM Systems, Flipkart, Goldman Sachs, Guidewire, Infosys, Intuit, J.P. Morgan, LinkedIn, Morgan Stanley, Nvidia, Oracle, PayPal, Pocket Gems, Qualcomm, SAP, SIG, Salesforce, Samsung, ServiceNow, Spotify, Turing, Verily, Walmart Labs, Wipro, Yandex, eBay.

Kth Largest Element in an Array | LeetCode 215

Medium

Array Divide and Conquer Sorting Heap (Priority Queue)Quickselect

Time: O(n)Space: O(1)

Solution Code

Available in:

import java.util.Random;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int target_index = n - k;
        
        int left = 0, right = n - 1;
        Random random = new Random();
        
        while (left <= right) {
            int pivot_idx = left + random.nextInt(right - left + 1);
            int pivot_val = nums[pivot_idx];
            
            // Move pivot to the end
            int temp = nums[pivot_idx];
            nums[pivot_idx] = nums[right];
            nums[right] = temp;
            
            int store_idx = left;
            for (int i = left; i < right; i++) {
                if (nums[i] < pivot_val) {
                    int temp2 = nums[store_idx];
                    nums[store_idx] = nums[i];
                    nums[i] = temp2;
                    store_idx += 1;
                }
            }
            
            // Move pivot to its final sorted position
            int temp3 = nums[right];
            nums[right] = nums[store_idx];
            nums[store_idx] = temp3;
            
            if (store_idx == target_index) {
                return nums[store_idx];
            } else if (store_idx < target_index) {
                left = store_idx + 1;
            } else {
                right = store_idx - 1;
            }
        }
        return -1; // Should not reach here, but added for compilation
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 215: Kth Largest Element in an Array - Detailed explanation and solution approaches.

Topics

Array Divide and Conquer Sorting Heap (Priority Queue)Quickselect

Companies

AMDAccentureAvitoByteDanceCoupangDeloitteDeutsche BankEPAM Systems

Stats

Difficulty:Medium

Languages:4

Companies:33

Problem #:215

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Calculate the target index: `target_index = n - k`, where `n` is the length of the input array `nums`. This index represents the position of the k-th largest element in the sorted array.
2
Step 2: Initialize `left` and `right` pointers to the start and end of the array, respectively. These pointers define the search space within the array.
3
Step 3: While `left` is less than or equal to `right`, perform the following steps (the core Quickselect logic):
4
Step 4: Choose a random pivot index `pivot_idx` within the current search space (`left` to `right`). This helps to avoid worst-case scenarios for skewed arrays.
5
Step 5: Move the pivot element to the end of the current search space by swapping `nums[pivot_idx]` and `nums[right]`.
6
Step 6: Initialize `store_idx` to `left`. This index will keep track of the boundary between elements smaller than the pivot and elements greater than or equal to the pivot.
7
Step 7: Iterate through the current search space from `left` to `right - 1`. For each element `nums[i]`, if it's less than the `pivot_val`, swap it with the element at `nums[store_idx]` and increment `store_idx`.
8
Step 8: After the loop, swap the pivot element (currently at `nums[right]`) with the element at `nums[store_idx]`. This places the pivot element in its final sorted position within the current search space.
9
Step 9: Check if `store_idx` is equal to `target_index`. If so, the k-th largest element is `nums[store_idx]`, and we return it.
10
Step 10: If `store_idx` is less than `target_index`, the k-th largest element is in the right partition, so update `left = store_idx + 1` and continue the loop.
11
Step 11: If `store_idx` is greater than `target_index`, the k-th largest element is in the left partition, so update `right = store_idx - 1` and continue the loop.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is derived from the partitioning process. In the average case, each partition reduces the problem size by a constant factor. The space complexity is constant because the algorithm uses a fixed amount of extra space regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting

Sort the array in descending order and return the element at index k-1.

Time: O(n log n)Space: O(1) if an in-place sorting algorithm like Heapsort is used, O(n) otherwise.

Trade-offs: Sorting is simpler to implement but less efficient than Quickselect for large arrays, especially when k is small compared to n.

Heap (Priority Queue)

Use a min-heap of size k to store the k largest elements seen so far. Iterate through the array. If the current element is larger than the smallest element in the heap, replace the smallest element with the current element and re-heapify.

Time: O(n log k)Space: O(k)

Trade-offs: Heap-based solution is efficient when k is much smaller than n. It's also suitable if the input is received as a stream of data.

✨

Key Insights

1Insight 1: The problem can be solved without fully sorting the array, leading to a more efficient solution than using standard sorting algorithms.
2Insight 2: Quickselect algorithm provides an efficient way to find the k-th largest element by partitioning the array around a pivot, similar to Quicksort.
3Insight 3: Randomly choosing the pivot helps to avoid worst-case time complexity scenarios, especially for potentially skewed input arrays.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty array or invalid k. The code implicitly handles this due to the loop condition. If nums is empty, or k is larger than the length of nums, the while loop won't execute as `left` starts at 0 and `right` starts at `n-1`, so `left <= right` will be false initially. An invalid k value should also be validated before calling the function.
Edge case 2: Duplicate elements. The Quickselect algorithm handles duplicate elements correctly because the partitioning process correctly places elements equal to the pivot on either side of the pivot. This ensures the correct k-th largest element is identified, even if duplicates exist.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting that the problem asks for the k-th largest element, not the k-th distinct element. Some may try to remove duplicates first, which is unnecessary and inefficient.

✗Common mistake 2: Not handling edge cases such as an empty input array or an invalid value of k.

✗Common mistake 3: Not choosing a random pivot, which can lead to O(n^2) time complexity for skewed input arrays.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Finding the top k most frequent words in a document or a corpus of documents. This is used in natural language processing and information retrieval.

🏦Real-world scenario 2: Identifying the k most valuable customers based on their purchase history. This is used in customer relationship management (CRM) and marketing.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 6, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Kth Largest Element in an Array"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether divide and conquer techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?