Reading time: 15 minutes | Coding time: 5 minutes

We are given an integer array of size N or we can say number of elements is equal to N. We have to find the smallest/ minimum element in an array. The time complexity to solve this is linear O(N) and space compexity is O(1).

Our efficient approach can be seen as the first step of insertion sort. In fact, this can be extended to find the k-th smallest element which will take O(K * N) time and using this to sort the entire array will take O(N^2) time.

If we have extra information, we can take its advantage to find the smallest element in less time. For example, if array is already sorted, we can find the smallest element in constant time O(1).

Efficient Approach

Firstly, program asks the user to input the values. So, user enter the size of array i.e. N and then enter the elements of array. Afterwards, program gives the output i.e. smallest element in the entered array.

• We assign the first element value to the temp variable.
• Then we compare temp with all other elements inside a loop.
• If the temp is smaller than all other elements,
• Then we return temp which store first element value as smallest element.
• But if the element is smaller than the temp,
• Then we store that element value into temp.
• This way temp will always store the smallest value.
• Then we return temp.

Time complexity: O(N) where there are N elements in the array
Space complexity: O(1)

Pseudocode

Following is the pseudocode:

smallest = array[i] // first element
for i from 1 to length(array):
    element_i = array[i]
    if smallest > element_i
        smallest = element_i
smallest // this is our answer

Implementation

Following is the C++ implementation of our approach:

#include <iostream>
using namespace std;
    
int findSmallestElement(int arr[], int n){
      int temp = arr[0];
   for(int i=0; i<n; i++) {
      if(temp>arr[i]) {
         temp=arr[i];
      }
   }
   return temp;
}
int main() {
   int n;
   cout<<"Enter the size of array: ";
   cin>>n; 
   int arr[n];
   cout<<"Enter array elements: ";
   for(int i=0; i<n; i++){
      cin>>arr[i];
   }
   int smallest = findSmallestElement(arr, n);
   cout<<"Smallest Element is: "<<smallest;
   return 0;
}

Input:

Enter the size of array: 5
Enter array elements: 11 9 18 88 101

Output:

Smallest Element is: 9

Explanation

The program asks the user to enter the size of array and the elements of an array. Once all the elements are stored in the array, the function is called by passing array and function take array size as argument.

Firstly in the function we assign the value of first element to a variable and then we compare that variable value with every other element of array. If the variable is smaller than all other elements, then we return variable which store first element value as smallest element. If any element is small than the variable then the value of that element is store into that variable and the loop continues until all the elements are traversed. This way we have the smallest element in the variable at the end of the loop. Then we return value of the variable from the function.

Other approach

Some other approaches/ insights are as follows:

• Using Sorting

We can sort the array in ascending order and get the element at the first position. Sorting usually takes O(N logN) time with O(1) space so this is slower than our illustrated approach.

Steps:

• Sort the array
• Answer is element at index 0

To understand sorting algorithms, go through this link: