Find the second largest and second smallest element in an Array | Explained

Need the second smallest and second largest in one array? We compare a clear two-pass “better” method with a one-pass optimal trick. Full intuition, commented code, dry runs, and Big-O analysis.

So let’s get started with the [Problem Link].

1. Problem statement

You are given an array a of length n.
Return a list [secondLargest, secondSmallest], where

• secondLargest = the second-largest distinct value in a
• secondSmallest = the second-smallest distinct value in a

All elements are distinct, and n ≥ 2.

2. Example

3. High-level idea

We need the top two and bottom two distinct numbers.
No sorting is required; a couple of variables can track them while we scan the array.

You may be interested in solving “Check if array is sorted or not”.

4. Better solution – two passes (O 2-pass)

4.1 Intuition

1. First pass – find the absolute smallest and largest.
2. Second pass – find the best remaining candidates that are
   • greater than the smallest (→ second-smallest) and
   • smaller than the largest (→ second-largest).

4.2 Code

from typing import List


def getSecondOrderElements(n: int, a: List[int]) -> List[int]:
    small = float("inf")
    second_small = float("inf")
    large = float("-inf")
    second_large = float("-inf")

    # -------- Pass 1 : absolute min & max --------
    for i in range(0, len(a)):
        small = min(small, a[i])
        large = max(large, a[i])

    # -------- Pass 2 : second min & second max --------
    for i in range(0, len(a)):
        if a[i] < second_small and a[i] != small:      # candidate > min
            second_small = a[i]
        if a[i] > second_large and a[i] != large:      # candidate < max
            second_large = a[i]

    return [second_large, second_small]

4.3 Step-by-step explanation

• First loop sets small and large.
• Second loop revisits each value:
  • If it beats the current second_small but is not the absolute min → update.
  • If it beats the current second_large but is not the absolute max → update.
• Return the two found numbers.

4.4 Dry run (array [5, 1, 3, 4, 2])

Return [4, 2].

4.5 Complexity

• Time: O(n) + O(n) = O(2n) → O(n) (linear).
• Space: O(1).

5. Optimal solution – one pass (O 1-pass)

5.1 Why faster?

We can update both first- and second-rank variables on the same walk with carefully chosen if–elif ladders.

5.2 Code

from typing import List


def getSecondOrderElements(n: int, a: List[int]) -> List[int]:
    small = float("inf")
    second_small = float("inf")
    large = float("-inf")
    second_large = float("-inf")

    # -------- Single pass updates everything --------
    for i in range(0, len(a)):
        # ----- smaller side -----
        if a[i] < small:                       # new absolute min
            second_small = small
            small = a[i]
        elif a[i] < second_small and a[i] != small:
            second_small = a[i]

        # ----- larger side -----
        if a[i] > large:                       # new absolute max
            second_large = large
            large = a[i]
        elif a[i] > second_large and a[i] != large:
            second_large = a[i]

    return [second_large, second_small]

5.3 Step-by-step explanation

• Four sentinels start at ±infinity to simplify comparisons.
• For each value x:
  1. Left block checks the smaller side.
     • If x beats the current smallest, slide the old small down to second_small, then set small = x.
     • Else if x lands strictly between small and second_small, it becomes the new second_small.
  2. Right block handles the larger side in the same spirit.
     • If x exceeds large, push the old large down to second_large, then set large = x.
     • Else if x floats between second_large and large, it becomes the new second_large.

Because each block is separate, the same element may update both pairs when the array has only two numbers, exactly what we want.

5.4 Dry run on [9, 7]

Return [7, 9].

5.5 Complexity

• Time: O(n) – single scan.
• Space: O(1) – constant variables only.

6. Which one to choose?

For interviews, show the better solution first (clean concept), then improve to the optimal one to demonstrate refinement.

7. Key takeaways

• Tracking only two smallest / largest values lets you solve “second-order” problems in constant space.
• A clever ordering of if–elif statements collapses two passes into one without hurting readability.
• Always reset second variables before the first ones change, otherwise you lose information.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.