Python List Advanced Exercise - Find the k^th largest element in a list

Python List Advanced: Exercise-5 with Solution

Write a Python function to find the k^th largest element in a list.

Sample Solution-1:

The following function will return the k^th largest element in a list by sorting the list in descending order and returning the k^th element. This approach has a time complexity of O(n log n) due to the sorting operation. Additionally, sorting a list with a large number of unique elements might consume a lot of memory.

Python Code:

# Define a function to find the kth largest element in a list
def kth_largest_el(lst, k):
    # Sort the list in descending order (reverse=True)
    lst.sort(reverse=True)
    # Return the kth largest element (0-based index, so k-1)
    return lst[k - 1]

# Create a list of numbers
nums = [1, 2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list
print("Original list:")
print(nums)

# Initialize 'k' to 1
k = 1

# Iterate from k = 1 to k = 10
for i in range(1, 11):
    # Print a message indicating the value of 'k'
    print("kth largest element in the said list, when k =", k)
    
    # Call the kth_largest_el function with 'k' and print the result
    print(kth_largest_el(nums, k))
    
    # Increment 'k' by 1 for the next iteration
    k = k + 1 

Sample Output:

Original list:
[1, 2, 4, 3, 5, 4, 6, 9, 2, 1]
kth largest element in the said list, when k =  1
9
kth largest element in the said list, when k =  2
6
kth largest element in the said list, when k =  3
5
kth largest element in the said list, when k =  4
4
kth largest element in the said list, when k =  5
4
kth largest element in the said list, when k =  6
3
kth largest element in the said list, when k =  7
2
kth largest element in the said list, when k =  8
2
kth largest element in the said list, when k =  9
1
kth largest element in the said list, when k =  10
1

Flowchart:

What is the time complexity and space complexity of the following Python code?

def kth_largest_el(lst, k):
    lst.sort(reverse=True)
    return lst[k-1]

Time complexity – Here the code uses the built-in Python sort function, which has a time complexity of O(n log n), and then retrieves the kth largest element, which takes constant time. So, the time complexity of the given code is O(n log n), where n is the length of the input list "lst".

Space complexity - Here the code uses a constant amount of additional space regardless of the size of the input list “lst”. So, The space complexity of the code is O(1).

Sample Solution-2:

Python Code:

# Define a function to find the kth largest element in a list using quickselect algorithm
def quickselect(lst, k, start=0, end=None):
    # If 'end' is not specified, set it to the last index of the list
    if end is None:
        end = len(lst) - 1

    # Base case: If the 'start' position is greater than or equal to the 'end' position, return the element at the 'start' position
    if start >= end:
        return lst[start]

    # Find the pivot index using the partition function
    pivot_idx = partition(lst, start, end)

    # Compare 'k' with the pivot index to determine which side to search for the kth largest element
    if k == pivot_idx:
        return lst[k]
    elif k < pivot_idx:
        # Recursively search for the kth largest element in the left part of the partition
        return quickselect(lst, k, start, pivot_idx - 1)
    else:
        # Recursively search for the kth largest element in the right part of the partition
        return quickselect(lst, k, pivot_idx + 1, end)

# Define a function to partition a list and choose a pivot element
def partition(lst, start, end):
    # Choose the pivot element as the last element in the list
    pivot = lst[end]
    pivot_idx = start

    # Iterate through the list and move elements greater than the pivot to the left side
    for i in range(start, end):
        if lst[i] >= pivot:  # Compare elements with the pivot
            lst[i], lst[pivot_idx] = lst[pivot_idx], lst[i]
            pivot_idx += 1

    # Swap the pivot element to its correct position in the partition
    lst[end], lst[pivot_idx] = lst[pivot_idx], lst[end]

    # Return the pivot index
    return pivot_idx

# Create a list of numbers
nums = [1, 2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list
print("Original list:")
print(nums)

# Initialize 'k' to 1
k = 1

# Iterate from k = 1 to k = 10
for i in range(1, 11):
    # Print a message indicating the value of 'k'
    print("kth largest element in the said list, when k =", k)
    
    # Call the quickselect function with 'k-1' to find the kth largest element and print the result
    print(quickselect(nums, k - 1))
    
    # Increment 'k' by 1 for the next iteration
    k = k + 1 

Sample Output:

Original list:
[1, 2, 4, 3, 5, 4, 6, 9, 2, 1]
kth largest element in the said list, when k =  1
9
kth largest element in the said list, when k =  2
6
kth largest element in the said list, when k =  3
5
kth largest element in the said list, when k =  4
4
kth largest element in the said list, when k =  5
4
kth largest element in the said list, when k =  6
3
kth largest element in the said list, when k =  7
2
kth largest element in the said list, when k =  8
2
kth largest element in the said list, when k =  9
1
kth largest element in the said list, when k =  10
1

Flowchart:

What is the time complexity and space complexity of the following Python code?

def quickselect(lst, k, start=0, end=None):
    if end is None:
        end = len(lst) - 1
    if start >= end:
        return lst[start]
    pivot_idx = partition(lst, start, end)
    if k == pivot_idx:
        return lst[k]
    elif k < pivot_idx:
        return quickselect(lst, k, start, pivot_idx - 1)
    else:
        return quickselect(lst, k, pivot_idx + 1, end)

def partition(lst, start, end):
    pivot = lst[end]
    pivot_idx = start
    for i in range(start, end):
        if lst[i] >= pivot:  
            lst[i], lst[pivot_idx] = lst[pivot_idx], lst[i]
            pivot_idx += 1
    lst[end], lst[pivot_idx] = lst[pivot_idx], lst[end]
    return pivot_idx

Time complexity - The time complexity of the “quickselect” function depends on the partitioning algorithm used and a worst-case time complexity of O(n^2). In this case, the partitioning algorithm used is the "Lomuto partition scheme," which has an average time complexity of O(n).
The partition function has a time complexity of O(n), where n is the length of the sublist being partitioned.

Lomuto partition scheme : This scheme is attributed to Nico Lomuto. In most formulations this scheme chooses as the pivot the last element in the array. The algorithm maintains index i as it scans the array using another index j such that the elements at lo through i-1 (inclusive) are less than the pivot, and the elements at i through j (inclusive) are equal to or greater than the pivot.

Space complexity - Each recursive call creates a new stack frame, which takes up space on the call stack. So, the space complexity of both functions is O(log n) due to the recursive calls made by the “quickselect” function. In the worst case, “quickselect” can make O(n) recursive calls, resulting in a space complexity of O(n). However, the average case space complexity is O(log n) due to the "randomized" nature of the partitioning algorithm used.

Python Code Editor:

Previous: Find the k^th largest element in a list.
Next: Check if a list is a palindrome or not.