Technical Interviews Walkthrough: Find the Kth largest element in a given array.

Photo by Chris Ried on Unsplash

Well, If one of your career ambitions is to work as a software engineer with tech companies like Google, Facebook, Microsoft, Amazon, Apple, Netflix, etc, then the probability that you will come across this question in at least one technical interview is well over 80%.

True, this question looks simple from a glance but during your interviews at the FAANG companies, your interviewer doesn’t just want a solution to the problems thrown at you, they want the best possible solution to the problem in terms of time and space complexity.

Example: Given an array of integers {2, 4, 1, 3, 6, 7},

Question: Write a program to find the 3rd largest element in the array.

Program Output: 4.

There are a few reasons why interviewers like asking this question during technical interviews, some of the obvious reasons are outlined below

  • This question tests your understanding of the array data structure
  • This question has various solutions with different runtime.
  • Getting an optimal solution to this question will mean that one has a good understanding of algorithmic complexities and analysis

In this article, we will,

1. Look at three different solutions to this problem

2. Analyze the time complexity of each solution

3. Establish an optimal solution to the problem

4. Implement the optimal solution to the problem in a programming language

Tech Lead ranked this as the second most “difficult” coding interview problem

Three possible solutions to this problem

One possible solution to this problem will be to completely loop through the entire array of size N, K times in order to get the Kth largest element.

For instance, Given the initial array {2, 4, 1, 6, 7}.

  • Loop through the array from 2 to 7, then store the first largest element which is 7.
  • Loop through the array for the second time, then store the 2nd largest element, which is 6.
  • Loop through the array continuously, for K times in order to get the Kth largest element in the array.

This solution does not scale hence we won’t implement it here. It has a running time of K*N, which in the worst-case gives a runtime of O(n²).

A more efficient way to solve this problem will be to first sort the array with a super-fast sorting algorithm and get the element at the kth index of the array, which will be the kth largest element.

The fastest sorting algorithm, Quicksort has a runtime of O(N log N), so we can sort the array using this algorithm and then index into the array to get the kth largest element at constant time O(1).

For instance, Given the intial array {2, 4, 1, 6, 7},

1.Sort the array to {7, 6, 4, 2, 1}

2.Index into the kth position of the array to get the kth largest value in the array

The time complexity of this solution is directly proportional to the time taken to sort the array, which is O(N log N). This is not the best solution, hence we will not implement it in this article.

Note: You can implement the array sorting using any programming language system sort. The majority uses the quicksort algorithm.

Theoretically, this is the best possible(optimal) solution to this problem and we can prove this by using mathematical induction. In lame terms this approach has to do with selecting a random element in the array, putting this element in it’s ordered position in the array, and then returning the index j to that element.

This logic is called partitioning, and it is based on the quicksort portioning algorithm. You can read about it here.

After this index is returned we follow three simple steps

1. If the returned index j matches k, then element at j is the kth largest element in the array.

2. If the returned index j, is less than k, then partition 0 to j-1.

3. If the returned index j, is greater than k, then partition j+1 to N.

Before implementing the algorithm, note that in the array partitioning, we have to maintain two constraint

  • All element to the left of the partitioning element is less than the partitioning element.
  • All element to the right of the partitioning element is greater than the partitioning element.

If these constraints are met, it means the element in which the array was partitioned around is in its ordered position in the array.

Client API to get the Kth largest value in an array.
Partitioning algorithm.

To understand more about this partitioning technique please read this.

In this article, we walked through three possible solutions to the infamous technical interview question of finding the Kth largest element in an array of size N.

We analyzed the time complexities of each solution and established the most efficient solution with a runtime of O(log N).

The full java program for this problem can be found here.

I create, code and write about digital algorithms