When it comes to coding interviews, some problems appear deceptively simple at first glance. One such classic example is finding the “second minimum” value in an array or list of integers. While it sounds straightforward, this problem has a knack for exposing subtle gaps in logic and catching even experienced candidates off guard.

In this article, we’ll dive into this frequently asked question, explore its nuances, and discuss how to solve it effectively.

The Problem

You’re given a list of integers, and your task is to find the second smallest (second minimum) number in the list. At first, it seems like a breeze: iterate through the list, keep track of the smallest and second smallest values, and you’re done. However, hidden pitfalls make this problem trickier than it initially seems.

Let’s break it down:

  1. The list may contain duplicates.
  2. The list might include edge cases like negative numbers, zeros, or only one element.
  3. Ambiguities can arise depending on whether “second minimum” should account for unique values or not.

These questions emphasize the importance of understanding the problem statement thoroughly before diving into the code.

Assumption 1:

Duplicates are allowed, and second minimum can be the same as the smallest number. Return -1 if no second minimum exists.

Examples:

Input Output Reasoning
[1, 1, 2] 1 Second minimum is the duplicate of the smallest value.
[-5, -1, -3] -3 All negative numbers.
[3, 4, 4] 4 Second minimum is the duplicate of the next smallest value.

Solution of Assumtion 1

Let’s look at a simple Java solution:

public static int secondMin(List<Integer> inputList) {
    // Initialize with maximum possible values
    int min = Integer.MAX_VALUE;
    int secondMin = Integer.MAX_VALUE;

    for(int num : inputList){
        if(num <= min){
            secondMin = min; // Update secondMin before updating min
            min = num;
            System.out.println("num :"+num+" , num <= min, min:"+ min+" secondMin:"+ secondMin);
        }
        else {
            if(num < secondMin){
                secondMin = num;
                System.out.println("num :"+num+" , num > min && num < secondMin, min:"+ min+" secondMin:"+ secondMin);
            }
            System.out.println("num :"+num+ " , num > min, min:"+ min+" secondMin:"+ secondMin);
        }
    }
    // Handle edge case: if secondMin was never updated
    return secondMin == Integer.MAX_VALUE ? -1 : secondMin;
}

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(1, 1, 2);
    System.out.println("Second Minimum: " + secondMin(list)); // Output: 1
}

Output:

num :1 , num <= min, min:1 secondMin:2147483647
num :1 , num <= min, min:1 secondMin:1
num :2 , num > min, min:1 secondMin:1
Second Min: 1

Assumption 2:

Second minimum must be distinct from the smallest number. Return -1 if no distinct value exists.

Examples:

Input Output Reasoning
[1, 1, 2, 3] 2 Next distinct value greater than the smallest (1).
[1, 1, 1] -1 No distinct second minimum exists.
[1, 2, 2, 3] 2 Second minimum is distinct and next smallest value.

Solution of Assumtion 2

public static int secondMin2(List<Integer> inputList) {
    // Initialize with maximum possible values
    int min = Integer.MAX_VALUE;
    int secondMin = Integer.MAX_VALUE;

    for(int num : inputList){
        if(num < min){
            secondMin = min; // Update secondMin before updating min
            min = num;
            System.out.println("num :"+num+" , num < min, min:"+ min+" secondMin:"+ secondMin);
        }
        else {
            if(num > min && num < secondMin){
                secondMin = num; // Update secondMin only if num is greater than min and smaller than current secondMin
                System.out.println("num :"+num+" , num > min && num < secondMin, min:"+ min+" secondMin:"+ secondMin);
            }
            else
                System.out.println("num :"+num+ " , num = min or num = secondMin or num > secondMin , min:"+ min+" secondMin:"+ secondMin);


        }
    }

    // Handle edge case: if secondMin was never updated
    return secondMin == Integer.MAX_VALUE ? -1 : secondMin;
}

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(1, 1, 2, 2, 3);
    System.out.println("Second Minimum: " + secondMin2(list)); // Output: 2
}

Output:

num :1 , num < min, min:1 secondMin:2147483647
num :1 , num = min or num = secondMin or num > secondMin , min:1 secondMin:2147483647
num :2 , num > min && num < secondMin, min:1 secondMin:2
num :2 , num = min or num = secondMin or num > secondMin , min:1 secondMin:2
num :3 , num = min or num = secondMin or num > secondMin , min:1 secondMin:2
Second Min: 2

Explanation: For the input list [1, 1, 2, 2, 3], the smallest (min) is 1 and the second smallest (secondMin) is 2 as we are looking for distinct elements for min and seconMin, and for [1, 1, 1], it logically outputs -1 because there is no distinct second minimum.

The condition num > min && num < secondMin ensures that secondMin is updated only when the value is strictly greater than min. This way, duplicates of the minimum are ignored, and we move on to find the next distinct value.

Efficiency:

The solutions discussed above run in O(n) time complexity and use O(1) additional space, making them efficient for larger input sizes.

Conclusion

The second minimum problem is a prime example of how coding interviews test more than just technical prowess—they challenge your ability to think critically, handle edge cases, and write solutions that are both efficient and robust. By focusing on clarifying assumptions, validating inputs, and learning from debugging, developers can strengthen their problem-solving skills and approach similar challenges with confidence.

Author: Mohammad J Iqbal

Mohammad J Iqbal

Follow Mohammad J Iqbal on LinkedIn