Find the second largest number in an array in one pass.

Find the second largest element of an array in a single pass, handling duplicates, negative numbers and arrays with fewer than two distinct values.

0 0
Read Time:1 Minute, 31 Second

Sorting and taking the second last element works, but costs O(n log n) and fails on duplicates. The interviewer wants one pass with two variables.

One pass, two variables

static Integer secondLargest(int[] a) {
    if (a == null || a.length < 2) return null;
    long first = Long.MIN_VALUE, second = Long.MIN_VALUE;
    for (int x : a) {
        if (x > first) {
            second = first;
            first = x;
        } else if (x > second && x < first) {
            second = x;
        }
    }
    return second == Long.MIN_VALUE ? null : (int) second;
}

Why it is written this way

  • When a new largest arrives, the old largest becomes second: that is the line second = first.
  • x < first skips duplicates of the largest, so [5, 5, 3] gives 3, not 5.
  • Starting from Long.MIN_VALUE instead of 0 handles all-negative arrays such as [-4, -2, -9], which gives -4.
  • Using long for the trackers means a real Integer.MIN_VALUE in the array is not confused with “not found”. Returning null covers arrays like [7, 7, 7] with no second distinct value.

Time O(n), space O(1).

Dry run on [12, 35, 1, 10, 34, 1]

x=12  first=12 second=-inf
x=35  first=35 second=12
x=1   no change
x=10  no change
x=34  second=34
x=1   no change
answer: 34

Follow-ups

  • Find the kth largest: use a min-heap of size k (O(n log k)) or Quickselect (O(n) on average).
  • Find the second smallest: flip the comparisons.
  • What if the array is a stream you cannot store?

This answer was written by Debugger’s Space as practice material. It is asked in most Indian IT services interviews (TCS, Infosys, Wipro, HCLTech, Tech Mahindra, LTIMindtree, Accenture, Cognizant, Capgemini, IBM). See each company’s hiring steps and practice questions on Debugger’s Space.

Previous post Reverse a string without using a built-in reverse function.
Next post Check whether two strings are anagrams.
Subscribe
Notify of
guest

0 Comments
Oldest
Newest Most Voted
Close
0
Would love your thoughts, please comment.x
()
x