CA 07 - 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)

In this approach, we first loop until range(k) because we want to find the kth smallest element. By initializing min_val to the first element, we can iterate throughout the array arr using for loop j and find the actual minimum value of the iteration. When a value less then the considered value is found, we replace min_val with the actual minimum value. At the end of the loop, we remove the smallest element index so that in the next iteration, the same smallest value will not be returned after the iteration. Finally, we can display the min_val which will contain the kth smallest element.