The programming logic for finding the smallest number is easy. However, what if you want to find the second smallest number? This blog covers two different ways to find the second smallest number in the list by using Python.
Method 1 (simple but inefficient): By sorting array
The first program is the standalone program, where the user is asked to populated the list during run time. Then sort the list using pythons build-in sorted function and return the second element which is the second smallest one. Time complexity of this method is O(n Log n).
arr = [5,2,4,9,7,2]
def printSecondLowest(arr):
#Array must have at least two elements else second lowest cannot be found
if len(arr) > 1:
sec_low = sorted(set(arr))[1]
print('The second lowest element of array is:', sec_low)
else:
print('Invalid input: Array with only one element')
printSecondLowest(arr)
Efficient: Compare each element with current smallest & second smallest & updated if its smaller than second smallest
Yes, we can write an algorithm that finds second lowest element that time complexity of O(n).
Efficient algorithm
- If the number of element of array is less than 2, second lowest number doesn’t exist.
- Initialize first_low and second_low variable to very high value say 100**100 or maximum of the array.
- For each element of array do the following
- If element is lower than first_low
- second_low = first_low
- first_low = element
- else if the element is between first and second
- second_low = element
- If element is lower than first_low
- At the end if second_low and first_low are equal
- All elements are same and hence second lowest doesn’t exist
- Else second lowest element is second_low
def findSecondSmallest(arr):
#Array must have at least two elements else second lowest cannot be found
arr_size = len(arr)
max_num = 100**1000
if arr_size < 2:
print ('Invalid input: Array with only one element')
return
# Setting the first and second element to very high value, you can also set it to max(arr)
first_low = second_low= max_num
for element in arr:
# If current element is smaller than first_low then
# update both first_low and second_low
if element < first_low:
second_low = first_low
first_low = element
# Else if the current element is in between first_low & second_low then
# update second_low
elif (element < second_low and element != first_low):
second_low = element;
# In case all the elements are same, there is no second lowest
if (second_low == first_low):
print('All element of list is same so second smallest element found')
else:
print('The smallest element is: ',first_low,'and the second smallest element is: ',second_low)
# Driver function to test above function
arr = [12, 13, 1, 10, 34, 1]
findSecondSmallest(arr)