Find the Second Smallest Element in an Array: 3 C++ Approaches

Three C++ methods exist for finding the second smallest element in an array, and their time complexities differ enough to matter in a placement technical round.

The sorting approach takes O(n log n). The two-pass linear scan takes O(n) with two traversals. The single-pass linear scan takes O(n) with one traversal and O(1) extra space. Placement interviewers almost always expect the single-pass version, but knowing all three lets you answer “what are the trade-offs?” without pausing.

The Problem and Its Constraints

Given a non-empty array of integers, find the second smallest element.

• Input: arr = {12, 3, 5, 7, 19}
• Expected output: 5

Two definitions are in common use. Some problems mean the second smallest distinct value, so {3, 3, 5} returns 5. Others mean the second element in sorted order including duplicates, so {3, 3, 5} returns 3. The code in this article uses the distinct definition, which is the more common framing in placement and coding-round contexts. Confirm the definition with the interviewer before writing the first line.

Three boundary conditions come up in every serious technical screen:

• Array has exactly two elements: the larger of the two is the answer.
• All elements are identical: no valid second distinct smallest element exists.
• Array contains negative integers: initialise both tracking variables to INT_MAX, not zero.

Method 1: Sort the Array

Sort in ascending order. The element at index 1 is the second smallest.

#include <iostream>
#include <algorithm>
using namespace std;

void findSecondSmallestBySort(int arr[], int n) {
    sort(arr, arr + n);
    cout << "Second smallest: " << arr[1] << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    findSecondSmallestBySort(arr, n);
    return 0;
}

Output: Second smallest: 5

std::sort runs in O(n log n) and operates in-place, so the original array is modified. For {3, 3, 5, 7}, arr[1] after sorting returns 3, not 5. The sort-based approach does not skip duplicates. Use this method when the sorted order is needed for a subsequent step. Sorting to retrieve a single value when O(n) is achievable is a trade-off worth flagging in an interview.

Method 2: Two-Pass Linear Scan

First pass: find the smallest element. Second pass: find the smallest element strictly greater than it.

#include <iostream>
#include <climits>
using namespace std;

void findSecondSmallestTwoPass(int arr[], int n) {
    int first = INT_MAX, second = INT_MAX;

    for (int i = 0; i < n; i++)
        if (arr[i] < first) first = arr[i];

    for (int i = 0; i < n; i++)
        if (arr[i] > first && arr[i] < second) second = arr[i];

    if (second == INT_MAX)
        cout << "No distinct second smallest element." << endl;
    else
        cout << "Second smallest: " << second << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    findSecondSmallestTwoPass(arr, n);
    return 0;
}

Output: Second smallest: 5

INT_MAX is the largest value a signed 32-bit integer can hold. Using it as the initial sentinel means any real array element replaces it on first comparison. If second is still INT_MAX after both loops, no distinct second smallest element exists. See cppreference for <climits> and INT_MAX for the full constant list.

This approach reads the array twice. Correct and readable, but the single-pass method below does the same work in one traversal.

Method 3: Single-Pass Linear Scan

Maintain two variables and update both in one loop. This is the method to reach for in a time-pressured coding round.

#include <iostream>
#include <climits>
using namespace std;

void findSecondSmallestSinglePass(int arr[], int n) {
    int first = INT_MAX, second = INT_MAX;

    for (int i = 0; i < n; i++) {
        if (arr[i] < first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > first && arr[i] < second) {
            second = arr[i];
        }
    }

    if (second == INT_MAX)
        cout << "No distinct second smallest element." << endl;
    else
        cout << "Second smallest: " << second << endl;
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    findSecondSmallestSinglePass(arr, n);
    return 0;
}

Output: Second smallest: 5

Walk through with arr = {12, 3, 5, 7, 19}:

• i=0, value=12: 12 is less than INT_MAX. Set second = INT_MAX, first = 12.
• i=1, value=3: 3 is less than 12. Set second = 12, first = 3.
• i=2, value=5: 5 is greater than 3 and less than 12. Set second = 5.
• i=3, value=7: 7 is greater than 3 but not less than 5. No change.
• i=4, value=19: 19 is greater than 3 but not less than 5. No change.
• Result: second = 5.

The > (not >=) in the else if condition is intentional: it skips elements equal to first, keeping the result as the second smallest distinct value.

Complexity and Trade-off Summary

Method	Time	Space	Modifies array	Passes through array
Sort and index	O(n log n)	O(1) in-place	Yes	1 sort pass
Two-pass scan	O(n)	O(1)	No	2
Single-pass scan	O(n)	O(1)	No	1

For placement coding rounds, state the single-pass O(n) approach as the default answer. Mention the sort-based approach only to explain why it is suboptimal.

Edge Cases Every Interviewer Tests

Four boundary inputs come up in placement tests and online coding assessments:

• All elements identical ({5, 5, 5}): second stays INT_MAX and is never updated. Add a guard after the loop and print a “no distinct second smallest” message rather than returning INT_MAX.
• Only two distinct values ({7, 3, 7, 3}): first = 3, second = 7. Both linear methods handle this correctly.
• Only two elements ({4, 9}): first = 4, second = 9. No special handling needed.
• Negative values ({-2, -5, 0, 3}): INT_MAX as sentinel works for any signed integer. Result: first = -5, second = -2.

The sort-based approach does not require an INT_MAX guard, but arr[1] after sorting returns the minimum value for an all-identical array; technically the second position in sorted order, not a distinct second smallest.

Where This Problem Shows Up in Placement Tests

Array-traversal problems at this level appear in TCS NQT coding sections, Wipro NLTH technical rounds, and most service-tier on-campus drives. The framing varies: “find the Kth smallest”, “print elements between minimum and second minimum”, “solve without modifying the array”. The single-pass update pattern is the shared core across all of them.

The related find smallest and largest element in an array problem extends this technique to tracking both bounds simultaneously in O(n). For broader coverage of what comes up across rounds, 20 most-asked data structures interview questions covers the array, linked list, tree, and hash-table problems that appear most often across service and product companies. The same sentinel-pair update logic appears in the flower sticks bouquet problem too. There, the tracked value is a split index instead of a minimum.

Once O(n) traversals feel automatic, the next test is whether you can explain the duplicate-case logic to a model that might return INT_MAX for {3, 3, 3} and ask you to fix it. TinkerLLM (₹299) is a short-form sandbox for that kind of back-and-forth: you describe the edge case, the model proposes an approach, you test its logic against the inputs from this walkthrough. Faster feedback than resubmitting to an online judge.