Find smallest and second smallest elements in an array

Problem

Given an array of integers, our task is to write a program that efficiently finds the smallest and second smallest element present in the array.

This problem is similar to Find Second largest element in an array.

Examples

Example 1:

Input: arr[] = {12, 13, 1, 10, 34, 1}
Output: [1, 10]
Explanation: 1 is smallest and 10 is second smallest

Solution

Method 1 - Sorting

A Simple Solution is to sort the array in increasing order. The first two elements in sorted array would be two smallest elements. Time complexity of this solution is O(n Log n).

Method 2 - Two pass

A Better Solution is to scan the array twice. In first traversal find the minimum element. Let this element be x. In second traversal, find the smallest element greater than x. Time complexity of this solution is O(n). The above solution requires two traversals of input array.

Method 3 - One pass solution

An Efficient Solution can find the minimum two elements in one traversal. This is similar to Find Second largest element in an array.

public int[] findSecondSmallest(int[] arr) {
	int n = arr.length;

	if (n < 2) {
		return -1;
	}

	// Initialize variables
	int smallest = Integer.MAX_VALUE; // Initialize with largest possible integer value
	int secondSmallest = Integer.MAX_VALUE;

	for (int i = 0; i < n; i++) {
		// Update smallest and secondSmallest if necessary
		if (arr[i] < smallest) {
			secondSmallest = smallest;
			smallest = arr[i];
		} else if (arr[i] < secondSmallest && arr[i] != smallest) {
			secondSmallest = arr[i];
		}
	}

	int second = secondSmallest == Integer.MAX_VALUE ? -1 : secondSmallest;
	return new int[] {smallest, second};
}

Complexity

Time Complexity: O(n)