Find the Second-Largest Element Without Sorting

• Two trackers – maintain largest and secondLargest variables in a single pass.
• Demotion rule – when a new element beats the largest, the old largest becomes the second largest.
• Runner-up check – if the element is between the two trackers, update only secondLargest.
• O(n) time, O(1) space – one pass, two variables, far cheaper than sorting.
• Duplicate policy – decide whether to require the second largest to be strictly less than the largest.

What is the problem?

Given an array, find the second-largest element without sorting. In a banking context, the risk team at National Bank of India wants the second-highest transaction on Priya's account, because the largest is a predictable salary credit and the runner-up is the one they scrutinise.

How does the algorithm work?

Maintain two variables: largest and secondLargest. For each element, apply an ordered check. If the element beats the largest, demote the old largest to secondLargest and then set the element as the new largest. Otherwise, if the element is between the two, update only secondLargest.

package com.bank.service;

import java.math.BigDecimal;
import java.util.Optional;

public class RunnerUpFinder {

    public static Optional<BigDecimal> findSecondLargest(BigDecimal[] amounts) {
        if (amounts == null || amounts.length < 2) {
            return Optional.empty();
        }
        BigDecimal largest = amounts[0];
        BigDecimal secondLargest = null;

        for (int i = 1; i < amounts.length; i++) {
            if (amounts[i].compareTo(largest) > 0) {
                secondLargest = largest;
                largest = amounts[i];
            } else if (amounts[i].compareTo(largest) < 0) {
                if (secondLargest == null || amounts[i].compareTo(secondLargest) > 0) {
                    secondLargest = amounts[i];
                }
            }
        }
        return Optional.ofNullable(secondLargest);
    }

    public static void main(String[] args) {
        BigDecimal[] txns = {
            new BigDecimal("85000.00"),
            new BigDecimal("42500.75"),
            new BigDecimal("85000.00"),
            new BigDecimal("67200.50"),
            new BigDecimal("3100.25")
        };
        Optional<BigDecimal> result = findSecondLargest(txns);
        result.ifPresent(v -> System.out.println("Second largest: Rs." + v));
    }
}

Second largest: Rs.67200.50

Why is the demotion ordering critical?

You must copy the old largest into secondLargest before overwriting largest. If you update largest first, you lose the value that should become the runner-up. This is the single most common bug in this problem.

// Wrong: losing the old largest
largest = amounts[i];           // overwrites before demotion
secondLargest = largest;         // now secondLargest == amounts[i], not the old largest

// Correct: demote first
secondLargest = largest;         // save the old largest
largest = amounts[i];            // then overwrite

How do you handle duplicates?

The strict distinct version requires the second largest to be strictly less than the largest. The condition amounts[i].compareTo(largest) < 0 in the else-if branch skips duplicates of the maximum. If you allow duplicates, change the condition to <=.

What about edge cases?

An array with fewer than two elements has no second largest. An array where every element is identical has no distinct second largest. Returning Optional.empty() makes the absence explicit.

// All identical: [85000, 85000, 85000]
// largest = 85000, secondLargest remains null
// Optional.empty() is returned

What is the time and space complexity?

• Time: O(n) because one pass with a constant number of comparisons per element.
• Space: O(1) because only two tracking variables are used.
• Sorting would cost O(n log n), which is unnecessarily expensive for finding just two values.

What are common mistakes?

Besides the demotion ordering bug, another mistake is initialising both trackers with Integer.MIN_VALUE, which does not apply to BigDecimal. Another is returning zero instead of signalling the absence of a second largest.

// Wrong: returning zero when there is no second largest
if (secondLargest == null) return BigDecimal.ZERO; // misleading

// Correct: signal absence
return Optional.ofNullable(secondLargest);

How does this extend to finding the kth largest?

For k=2 the two-tracker approach is efficient and clean. For arbitrary k, the min-heap approach or Quickselect is more appropriate. A size-k min-heap finds the kth largest in O(n log k) time.

What should a senior engineer know?

A senior engineer uses Optional to model the possible absence of a second largest, making the API impossible to misuse. The senior also considers thread safety: if the array is being modified concurrently, the single-pass scan may read inconsistent data, so in a concurrent banking pipeline the array must be protected with a snapshot or a lock.