Find the Smallest and Second Smallest Element in an Array

Problem

Given an array of integers, your task is to find the smallest and second smallest element in the array. If smallest and second smallest do not exist, print -1.

Examples:

Example 1:

Input :
5
2 4 3 5 6
Output :
2 3 
Explanation: 
2 and 3 are respectively the smallest and second smallest elements in the array.

Example 2:

Input :
6
1 2 1 3 6 7
Output :
1 2 
Explanation: 
1 and 2 are respectively the smallest and second smallest elements in the array.

Your task:

You don't need to read input or print anything. Your task is to complete the function minAnd2ndMin() which takes the array A[] and its size N as inputs and returns a vector containing the smallest and second smallest element if possible, else return -1.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^5$
• $1<=A[i]<=10^5$

Solution

Python

def minAnd2ndMin(a, n):
    if n < 2:
        return [-1, -1]
    
    first_min = float('inf')
    second_min = float('inf')
    
    for num in a:
        if num < first_min:
            second_min = first_min
            first_min = num
        elif num < second_min and num != first_min:
            second_min = num
    
    if second_min == float('inf'):
        return [-1, -1]
    else:
        return [first_min, second_min]

Java

public long[] minAnd2ndMin(long a[], long n) {
    if (n < 2) {
        return new long[]{-1, -1};
    }
    long first_min = Long.MAX_VALUE;
    long second_min = Long.MAX_VALUE;
    for (long num : a) {
        if (num < first_min) {
            second_min = first_min;
            first_min = num;
        } 
        else if (num < second_min && num != first_min) {
            second_min = num;
        }
    }
    if (second_min == Long.MAX_VALUE) {
        return new long[]{-1, -1};
    } 
    else {
        return new long[]{first_min, second_min};
    } 
}

C++

vector<int> minAnd2ndMin(int a[], int n) {
   if (n < 2) {
        return {-1, -1};
    }
    int first_min = INT_MAX;
    int second_min = INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (a[i] < first_min) {
            second_min = first_min;
            first_min = a[i];
        } else if (a[i] < second_min && a[i] != first_min) {
            second_min = a[i];
        }
    }
    if (second_min == INT_MAX) {
        return {-1, -1};
    } 
    else {
        return {first_min, second_min};
    } 
}

C

void minAnd2ndMin(int a[], int n, int result[2]) {
    if (n < 2) {
        result[0] = -1;
        result[1] = -1;
        return;
    }
    int first_min = INT_MAX;
    int second_min = INT_MAX;
    for (int i = 0; i < n; ++i) {
        if (a[i] < first_min) {
            second_min = first_min;
            first_min = a[i];
        } 
        else if (a[i] < second_min && a[i] != first_min) {
            second_min = a[i];
        }
    }
    if (second_min == INT_MAX) {
        result[0] = -1;
        result[1] = -1;
    } 
    else {
        result[0] = first_min;
        result[1] = second_min;
    }
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$