Finding the Second Smallest Number in an Array

In this tutorial, we discuss how to find the second smallest number in an array using two different approaches.

Key Problem Statement

• Given an array, find the second smallest number.
• Example array: [-1, 7, 1, 18, 34]

Approach 1: Sorting the Array

1. Sorting Method

   • Sort the array.
   • The second smallest number will be located at index 1 after sorting.
   • For example, sorting the array [-1, 7, 1, 18, 34] results in [-1, 1, 7, 18, 34].
   • The second smallest number is 1 (element at index 1).

2. Time Complexity

   • This approach has a time complexity of O(n log n) due to sorting.

3. Limitation

   • If the array contains repeated values (e.g. [-1, -1, 1, 18, 34]), the result may be incorrect.

Approach 2: Linear Traversal

1. Traversal Method

   • Maintain two variables: smallest and second_smallest, initialized to Integer.MAX_VALUE.
   • Traverse the array and update these variables based on conditions.

2. Algorithm Steps

   • Start from index 0 of the array.
   • Check each element:
     • If the current element is smaller than smallest, update second_smallest to be smallest and then update smallest to the current element.
     • If the current element is greater than smallest and smaller than second_smallest, update second_smallest to the current element.

3. Example Walkthrough

   • For array [-1, 7, 1, 18, 34]:
     • Initialize: smallest = Integer.MAX_VALUE, second_smallest = Integer.MAX_VALUE.
     • After traversing -1: smallest = -1, second_smallest = Integer.MAX_VALUE.
     • After traversing 7: second_smallest = 7.
     • After traversing 1: second_smallest = 1.
     • Continue until the end of the array.
   • Final result is 1.

4. Time Complexity

   • This approach has a time complexity of O(n), which is more efficient.

5. Why Use Integer.MAX_VALUE

   • Using Integer.MAX_VALUE ensures that any element in the array will be less than the initial values of smallest and second_smallest, allowing for proper comparisons.
   • If 0 or negative values were used as initial values, incorrect results could arise if the smallest number in the array is less than the assigned initial value.

Conclusion

• The second approach is preferred due to its efficiency and reliability against repeated values.
• For more programming tutorials, subscribe to the channel or visit the website: webrewrite.com

Example Code Snippet

// Example method to find second smallest number
public static int findSecondSmallest(int[] arr) {
    int smallest = Integer.MAX_VALUE;
    int second_smallest = Integer.MAX_VALUE;
    
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < smallest) {
            second_smallest = smallest;
            smallest = arr[i];
        } else if (arr[i] > smallest && arr[i] < second_smallest) {
            second_smallest = arr[i];
        }
    }
    return second_smallest;
}