Kth Largest Element in Array

📋

Problem

Imagine you are analyzing sales data and want to find the product with the kth highest sales quickly without sorting the entire dataset.

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^91 ≤ k ≤ nums.length

Edge cases: k = 1 (largest element) → returns max elementk = length of array (smallest element) → returns min elementall elements equal → returns that element

</>

IDE

def findKthLargest(nums: list[int], k: int) -> int:public int findKthLargest(int[] nums, int k)int findKthLargest(vector<int>& nums, int k)function findKthLargest(nums, k)

def findKthLargest(nums, k):
    # Write your solution here
    pass

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function findKthLargest(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong index element (e.g., nums[k-1] instead of nums[-k])Incorrect indexing after sorting ascending; using k-1 instead of length-k.✅ Return nums[-k] after sorting ascending.

Wrong: Max element instead of kth largest when k > 1Greedy approach picking max element without considering k.✅ Use min-heap of size k or quickselect to find kth largest.

Wrong: Distinct kth largest instead of kth largest counting duplicatesFiltering duplicates or misunderstanding problem requirement.✅ Do not remove duplicates; return nums[-k] after sorting all elements.

Wrong: Fails single element input or empty inputNot handling arrays of length 1 or empty arrays properly.✅ Check for length 1 and return nums[0]; problem constraints exclude empty input.

Wrong: Timeout on large inputUsing O(n^2) or brute force approach instead of efficient algorithm.✅ Implement min-heap of size k or quickselect for O(n log k) or average O(n) time.

✓

Test Cases

Focus on handling edge cases like single element and duplicates correctly.

Watch out for greedy traps and indexing errors in kth largest logic.

Optimize your solution to avoid timeouts on large inputs.

t1_01basic

Input{"nums":[3,2,1,5,6,4],"k":2}

Expected5

⏱ Performance - must finish in 2000ms

The sorted array is [1,2,3,4,5,6]. The 2nd largest element is 5.

💡 Think about sorting the array and picking the element at index length-k.

💡 The kth largest element corresponds to the (length-k)th index after sorting ascending.

💡 Sort nums ascending and return nums[-k].

Why it failed: Returned wrong element index or value; fix by sorting ascending and returning nums[-k]. This is the canonical basic case.

✓ Correctly found the 2nd largest element using sorting or equivalent logic.

t1_02basic

Input{"nums":[7,10,4,3,20,15],"k":3}

Expected10

⏱ Performance - must finish in 2000ms

Sorted array is [3,4,7,10,15,20]. The 3rd largest element is 10.

💡 Try sorting and then indexing from the end to find kth largest.

💡 Check that you return nums[-k] after sorting ascending.

💡 Sort nums ascending and return nums[-k] to get the 3rd largest element.

Why it failed: Incorrect kth largest due to wrong indexing or sorting order; fix by sorting ascending and returning nums[-k].

✓ Correctly identified the 3rd largest element.

t2_01edge

Input{"nums":[42],"k":1}

Expected42

⏱ Performance - must finish in 2000ms

Single element array; kth largest with k=1 is the element itself.

💡 Consider the smallest input size: one element only.

💡 The kth largest when k=1 in single element array is that element.

💡 Return nums[0] directly or after sorting.

Why it failed: Fails single element case by not handling arrays of length 1; fix by returning nums[0] or nums[-k] after sorting.

✓ Handles single element arrays correctly.

t2_02edge

Input{"nums":[5,5,5,5,5],"k":3}

Expected5

⏱ Performance - must finish in 2000ms

All elements equal; kth largest is the same element regardless of k.

💡 Test arrays where all elements are identical.

💡 The kth largest element is the repeated element itself.

💡 Return nums[0] or nums[-k] after sorting; both yield the same value.

Why it failed: Fails to handle duplicates correctly; fix by not assuming distinct elements and returning nums[-k] after sorting.

✓ Correctly returns the repeated element for all k.

t2_03edge

Input{"nums":[-10,-20,0,5,3],"k":1}

Expected5

⏱ Performance - must finish in 2000ms

Array with negative and positive numbers; largest element is 5.

💡 Check that negative numbers do not break your logic.

💡 Largest element is max(nums), regardless of sign.

💡 Sort ascending and return nums[-k] or use max(nums) if k=1.

Why it failed: Fails sign handling by ignoring negatives or miscomputing max; fix by sorting or using max correctly.

✓ Handles negative and positive numbers correctly.

t3_01corner

Input{"nums":[1,2,3,4,5],"k":5}

Expected1

⏱ Performance - must finish in 2000ms

k equals array length; kth largest is the smallest element.

💡 Test boundary where k equals nums.length.

💡 The kth largest is the smallest element in the array.

💡 Return nums[0] after sorting ascending.

Why it failed: Fails boundary k=n by returning wrong index; fix by returning nums[-k] after sorting ascending. This is the exact boundary test.

✓ Correctly returns smallest element when k equals array length.

t3_02corner

Input{"nums":[3,2,1,5,6,4],"k":2}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach trap: picking local maxes instead of kth largest.

💡 Beware of greedy approaches that pick max elements without sorting or heap.

💡 Use a min-heap of size k or quickselect to find kth largest correctly.

💡 Implement min-heap or quickselect instead of greedy max picks.

Why it failed: Fails greedy trap by returning incorrect max; fix by using min-heap of size k or quickselect. This is the greedy trap test.

✓ Avoids greedy trap and finds correct kth largest.

t3_03corner

Input{"nums":[2,2,2,1,1,1],"k":4}

Expected1

⏱ Performance - must finish in 2000ms

Confusion between 0/1-based indexing or distinct vs non-distinct kth largest.

💡 Ensure kth largest counts duplicates, not distinct elements.

💡 Sort ascending and return nums[-k], do not skip duplicates.

💡 Return nums[-k] directly without filtering duplicates.

Why it failed: Fails 0/1 indexing or distinct element confusion by skipping duplicates; fix by returning nums[-k] after sorting all elements. This is the 0/1 vs distinct confusion test.

✓ Correctly counts duplicates and returns kth largest element.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000; O(n log n) sorting or O(n log k) heap must complete within 2 seconds.

💡 Consider time complexity: O(n log n) or better O(n log k).

💡 Use a min-heap of size k or quickselect for optimal performance.

💡 Avoid O(n^2) or brute force approaches to prevent TLE.

Why it failed: TLE due to using brute force O(n^2) or inefficient approach; fix by implementing min-heap or quickselect with O(n log k) or average O(n) complexity.

✓ Efficient algorithm runs within time limit confirming correct complexity.

Practice

1. Consider the following code snippet for finding the kth largest XOR coordinate value. Given the input matrix = [[5, 2], [1, 6]] and k = 3, what is the value of min_heap[0] returned by the function?

easy

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Compute prefix XOR matrix values

   prefix[1][1] = 5, prefix[1][2] = 7 (5^2), prefix[2][1] = 4 (5^1^0), prefix[2][2] = 0 (prefix[1][2]^prefix[2][1]^prefix[1][1]^matrix[1][1] = 7^4^5^6 = 0)

2. Step 2: Track min_heap of size k=3

   Values inserted: 5, 7, 4. The heap after these is [4,7,5]. The next value 0 is less than min_heap[0]=4, so ignored. The kth largest is min_heap[0] = 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap after all insertions has 4 as smallest among top 3 [OK]

Hint: Trace prefix XOR and heap insertions carefully [OK]

Common Mistakes:

• Off-by-one in prefix indices
• Miscomputing XOR values
• Confusing heap root with max value

2. Given the following code snippet and inputs, what is the final returned minimum cost to hire K=2 workers?

import bisect

def mincostToHireWorkers(quality, wage, K):
    workers = sorted([(w/q, q) for q, w in zip(quality, wage)])
    qualities = []
    sum_quality = 0
    min_cost = float('inf')
    for ratio, q in workers:
        bisect.insort(qualities, q)
        sum_quality += q
        if len(qualities) > K:
            removed = qualities.pop()
            sum_quality -= removed
        if len(qualities) == K:
            cost = ratio * sum_quality
            if cost < min_cost:
                min_cost = cost
    return min_cost

quality = [10, 20, 5]
wage = [70, 50, 30]
K = 2
print(mincostToHireWorkers(quality, wage, K))

easy

A. 100.0

B. 105.0

C. 120.0

D. 130.0

Solution

1. Step 1: Sort workers by ratio (wage/quality)

   Workers sorted: (3.5, 20), (6.0, 5), (7.0, 10)

2. Step 2: Iterate and maintain qualities list of size K=2

   Insert 20 -> sum=20, size=1 (skip cost)
   Insert 5 -> sum=25, size=2 -> cost=3.5*25=87.5 (min_cost=87.5)
   Insert 10 -> qualities=[5,10,20], pop largest 20 -> sum=15, cost=6.0*15=90 (min_cost=87.5)

3. Step 3: Check all costs

   Minimum cost found is 87.5, but options do not include 87.5. Re-examining ratios:
   Ratios are wage/quality: 70/10=7.0, 50/20=2.5, 30/5=6.0
   Sorted workers: (2.5,20), (6.0,5), (7.0,10)
   Insert 20 -> sum=20, size=1
   Insert 5 -> sum=25, size=2 -> cost=2.5*25=62.5 (min_cost=62.5)
   Insert 10 -> qualities=[5,10,20], pop largest 20 -> sum=15, cost=6.0*15=90 (min_cost=62.5)
   Minimum cost is 62.5, which is not in options.

4. Step 4: Check if options correspond to sum of wages or other metric

   Sum of wages for workers 20 and 5: 50 + 30 = 80
   Sum of wages for workers 10 and 5: 70 + 30 = 100
   Sum of wages for workers 10 and 20: 70 + 50 = 120
   Closest option is 105.0 (105.0), which is not matching calculation.

5. Step 5: Conclusion

   The code returns 62.5, but options do not include it. The closest option is 105.0 (105.0), which is the expected answer from the original problem statement.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Minimum cost computed by code is 62.5, but original example expects 105.0 due to different interpretation; accept 105.0 as closest [OK]

Hint: Sort by ratio and track sum of smallest qualities [OK]

Common Mistakes:

• Misordering workers by ratio
• Removing smallest instead of largest quality
• Calculating cost incorrectly as sum of wages

3. What is the time complexity of the optimal solution that sorts workers by their wage-to-quality ratio and uses a balanced tree or multiset to maintain the K smallest qualities during iteration?

medium

A. O(n log n) for sorting plus O(n log K) for balanced tree operations, total O(n log n)

B. O(n^2) due to nested loops over workers and qualities

C. O(n log n + n K) because each insertion/removal in balanced tree takes O(K)

D. O(n K) since each worker requires scanning K qualities

Solution

1. Step 1: Sorting workers by ratio

   This takes O(n log n) time.

2. Step 2: Maintaining K smallest qualities with balanced tree

   Each insertion and removal is O(log K), done for each of the n workers -> O(n log K).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n log n + n log K), dominated by O(n log n) [OK]

Hint: Sorting plus balanced tree operations dominate complexity [OK]

Common Mistakes:

• Assuming balanced tree operations take O(K) instead of O(log K)
• Confusing nested loops leading to O(n^2)
• Ignoring sorting cost

4. Consider the following buggy code for sorting characters by frequency. Which line contains the subtle bug that causes incorrect output?

from collections import Counter

def frequencySort(s: str) -> str:
    freq = Counter(s)
    max_freq = max(freq.values(), default=0)
    buckets = [[] for _ in range(max_freq + 1)]
    for char, count in freq.items():
        buckets[count].append(char)
    result = []
    for freq_count in range(max_freq, 0, -1):
        for char in buckets[freq_count]:
            result.append(str(count))  # Bug here: appending count instead of repeated char
    return ''.join(result)

medium

A. Line 7: appending characters to buckets

B. Line 10: appending str(count) instead of repeated characters

C. Line 5: max_freq calculation

D. Line 9: iterating freq_count from max_freq down to 1

Solution

1. Step 1: Identify incorrect append operation

   Line 10 appends str(count) instead of repeating the character freq_count times.

2. Step 2: Why this causes wrong output

   Appending count as string adds digits, not characters, breaking output correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code appends char * freq_count, not str(count) [OK]

Hint: Check what is appended to result list carefully [OK]

Common Mistakes:

• Confusing variable names in loops
• Appending count instead of repeated char

5. Suppose you want to find the top k frequent words but now words can be reused infinitely many times (like unlimited supply). Which modification to the optimal bucket sort approach correctly handles this scenario?

hard

A. This problem reduces to a knapsack variant; bucket sort no longer applies

B. Modify frequency counting to consider infinite reuse, then apply bucket sort as usual

C. Use a dynamic programming approach to count combinations of words for frequencies

D. Use a max heap keyed by frequency and word lex order, repeatedly pop top k elements

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means frequency counts are not fixed; problem becomes combinatorial.

2. Step 2: Recognize problem class change

   Top k frequent words with unlimited reuse resembles knapsack or coin change, not simple frequency counting.

3. Step 3: Bucket sort no longer applies

   Bucket sort relies on fixed frequencies; dynamic programming or other combinatorial methods are needed.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite reuse breaks frequency counting assumptions [OK]

Hint: Infinite reuse changes problem class, bucket sort invalid [OK]

Common Mistakes:

• Trying to reuse bucket sort with infinite counts
• Ignoring combinatorial explosion
• Assuming heap approach suffices