Kth Smallest

Problem Statement:
click here

Problem Understanding:
We are given an integer array arr[] and an integer k. The task is to return the kth smallest element in the array when arr[] is sorted.

Initial Approach:
My initial approach was to use the sort() function in Python so sort the array. Then by indexing arr[k-1] we can get the kth smallest element.

Example:
arr= [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
k = 4
arr.sort()
print(arr[k-1])

Sorted array:
arr= [2, 3, 4, 5, 6, 10, 10, 33, 48, 53]

Output:
5

Brute force approach:
Without using the in-built sort() function, we can achieve the same solution by:

arr = [7, 10, 4, 3, 20, 15]
k = 3

for i in range(k):     # for looping until smallest element k-1
    min_val = arr[0]   # assume first element is smallest
    min_index = 0      # since we assumed the first element

    for j in range(len(arr)): 
        if arr[j] < min_val:
            min_val = arr[j]
            min_index = j

    arr.pop(min_index) # remove the smallest element

print(min_val)

• First, I understood that I need the kth smallest element, not just the smallest.
• Then I thought: if I find the smallest element repeatedly, I can reach the kth one.
• So I decided to run a loop k times.
• In each iteration, I assumed the first available element as the minimum (min_val).
• Then I compared it with every other element in the array to find the actual minimum.
• Whenever I found a smaller value, I updated min_val.
• I also kept track of the index of this minimum element.
• After finding the smallest element in that iteration, I removed it so it won’t be used again.
• This ensures that the next iteration finds the next smallest element.
• I repeated this process until I completed k iterations.
• Finally, the last min_val I found is the kth smallest element.