Find the Kth Largest Integer in the Array

Medium

Amazon

2 views

Topics:

ArraysStrings

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the kth largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2nd largest integer in nums is "0".

Constraints:

1 <= k <= nums.length <= 10^4
1 <= nums[i].length <= 100
nums[i] consists of only digits.
nums[i] will not have any leading zeros.

Find the Kth Largest Integer in the Array

Medium

Amazon

2 views

Topics:

ArraysStrings

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the kth largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Example 1:

Input: nums = ["3","6","7","10"], k = 4
Output: "3"
Explanation:
The numbers in nums sorted in non-decreasing order are ["3","6","7","10"].
The 4th largest integer in nums is "3".

Example 2:

Input: nums = ["2","21","12","1"], k = 3
Output: "2"
Explanation:
The numbers in nums sorted in non-decreasing order are ["1","2","12","21"].
The 3rd largest integer in nums is "2".

Example 3:

Input: nums = ["0","0"], k = 2
Output: "0"
Explanation:
The numbers in nums sorted in non-decreasing order are ["0","0"].
The 2nd largest integer in nums is "0".

Constraints:

1 <= k <= nums.length <= 10^4
1 <= nums[i].length <= 100
nums[i] consists of only digits.
nums[i] will not have any leading zeros.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array?
What should I return if `k` is larger than the number of elements in the array?
Does the input array contain duplicate integers, and if so, should the kth largest integer consider duplicates (e.g., if the array is [3,2,1,2] and k=2, is the 2nd largest 2 or 3)?
Is `k` guaranteed to be a positive integer?
Can the input array be empty or null, and if so, what should I return?

Brute Force Solution

Approach

The brute force way to find the Kth largest number is pretty straightforward. We look at all the numbers and find a way to order them from largest to smallest, then simply pick the number in the Kth position.

Here's how the algorithm would work step-by-step:

First, we need to put the numbers in order from largest to smallest.
A simple way to do this is to repeatedly find the largest number in the bunch and set it aside.
Then, from the remaining numbers, we find the next largest and set it aside as well.
We keep doing this until we've identified all numbers from largest to smallest.
Once we have this ordered list, the Kth largest number is simply the number in the Kth position from the start of the list.

Code Implementation

def find_kth_largest_integer(numbers, k_value): 
    sorted_numbers = []
    working_numbers = numbers[:] 

    # Repeatedly find and extract the maximum
    while working_numbers:
        largest_number = working_numbers[0]
        largest_index = 0
        for index, number in enumerate(working_numbers):
            if number > largest_number:
                largest_number = number
                largest_index = index

        # Remove largest from the working set and add it to the sorted list
        sorted_numbers.append(working_numbers.pop(largest_index))

    # After sorting, return the kth largest
    return sorted_numbers[k_value - 1]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates to find the largest element n times. In each iteration, it searches through the unsorted portion of the array to find the maximum, which takes O(n) time. Since this search happens n times, the overall time complexity is O(n * n). Thus, the total operations can be approximated as n², resulting in a time complexity of O(n²).

Space Complexity

O(N) – The provided plain English explanation describes repeatedly finding the largest number and setting it aside. This implies building a fully sorted list of all numbers from largest to smallest. Since we are creating a new, ordered list, we need auxiliary storage space proportional to the number of input integers to hold this list. Where N is the number of integers in the input array, the space required is O(N).

Optimal Solution

Approach

To quickly find the Kth largest number, we don't need to sort the entire list. Instead, we use a clever strategy to focus only on the numbers that are most likely to be the Kth largest, discarding the rest.

Here's how the algorithm would work step-by-step:

Imagine organizing the numbers into groups based on their size, but without fully sorting them.
The goal is to quickly identify the group that would contain the Kth largest number if the list was fully sorted.
We repeatedly split the groups, each time throwing away the groups that are definitely too small or too big to contain the Kth largest.
This continues until only one number remains, which is the Kth largest number we were looking for.

Code Implementation

def find_kth_largest(numbers, k):
    def partition(numbers_list, left_index, right_index):
        pivot_value = numbers_list[right_index]
        i = left_index

        for j in range(left_index, right_index):
            if numbers_list[j] <= pivot_value:
                numbers_list[i], numbers_list[j] = numbers_list[j], numbers_list[i]
                i += 1

        numbers_list[i], numbers_list[right_index] = numbers_list[right_index], numbers_list[i]
        return i

    left_index = 0
    right_index = len(numbers) - 1

    # Adjust k to be 0-indexed
    k_index = len(numbers) - k

    while True:
        pivot_index = partition(numbers, left_index, right_index)

        # We found the kth largest element
        if pivot_index == k_index:
            return numbers[pivot_index]

        # Discard left side and search right side
        elif k_index > pivot_index:

            left_index = pivot_index + 1

        # Discard right side and search left side
        else:
            right_index = pivot_index - 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a selection algorithm similar to Quickselect, which on average partitions the array around a pivot and recursively searches in only one of the partitions. The partitioning step takes O(n) time, and on average, we reduce the search space by a constant factor in each step. The average case time complexity is therefore O(n) + O(n/2) + O(n/4) + ... = O(n * (1 + 1/2 + 1/4 + ...)) which converges to O(n). Although in the worst case scenario it degrades to O(n^2), the average performance is linear.

Space Complexity

O(1) – The algorithm described organizes numbers into groups and splits them without explicitly storing these groups in separate data structures. While conceptually we're 'discarding' groups, the plain English explanation does not imply creating new temporary lists or hash maps to represent these groups. The process focuses on identifying and potentially updating pointers or indices, leading to a constant amount of extra memory usage regardless of the input size N, where N is the total number of integers in the input array.

Edge Cases

Case	How to Handle
Null or empty input array	Return null or throw an IllegalArgumentException to indicate invalid input.
k is less than or equal to zero	Throw IllegalArgumentException as k must be a positive integer representing a valid rank.
k is greater than the array length	Return null or throw an IllegalArgumentException as the kth largest element doesn't exist.
Array contains duplicate integer strings	The sorting algorithm handles duplicates correctly, ensuring the correct kth largest is returned.
Array contains very large integer strings that may exceed integer limits	Use a comparator that performs lexicographical comparison to handle large integer strings correctly.
Array contains leading zeros in the integer strings	Handle them as normal strings; the lexographical sort still applies correctly
Array with all identical integer strings	The algorithm should still correctly identify the kth largest element, which will be the identical value.
Memory constraints with extremely large input array	Consider using a min-heap of size k to reduce memory footprint instead of sorting the entire array.