Second Largest Digit in a String - Video Solutions

Problem Overview: You are given an alphanumeric string that may contain letters and digits. Extract all digits and return the second largest distinct digit. If fewer than two distinct digits exist, return -1. The key detail is distinct digits — repeated values should only count once.

Approach 1: Using Set for Unique Values and Sorting (Time: O(n + k log k), Space: O(k))

Scan the string and collect every digit into a set. The set automatically removes duplicates, leaving only unique digit values. Convert the set into a list and sort it in descending order. The second element in the sorted list is the second largest digit. If the list size is less than two, return -1. This approach is straightforward and easy to reason about because the set handles uniqueness while sorting determines the ranking.

The number of possible digits is small (0–9), so sorting overhead is minimal in practice. Time complexity is O(n + k log k) where k is the number of distinct digits (at most 10). Space complexity is O(k). This solution is commonly implemented using structures from Hash Table concepts for uniqueness and basic String iteration.

Approach 2: Using Two Variables to Track Top Two Distinct Numbers (Time: O(n), Space: O(1))

Instead of storing digits, track the two largest distinct digits while scanning the string once. Maintain two variables: max1 (largest digit) and max2 (second largest digit). For every character, check if it is a digit. Convert it to an integer and update the two variables:

If the digit is greater than max1, shift max1 into max2 and update max1. If the digit is smaller than max1 but greater than max2, update max2. Skip updates when the digit equals max1 to preserve distinctness. After processing the entire string, max2 holds the answer or remains -1 if no second distinct digit exists.

This approach avoids extra storage and sorting. Every character is processed exactly once, giving O(n) time and O(1) space. The logic resembles common interview patterns where you track the top two elements during a single pass.

Recommended for interviews: Start by describing the set + sorting idea because it clearly shows how you enforce uniqueness. Then move to the single-pass two-variable approach. Interviewers usually prefer the O(n) scan because it demonstrates strong control over state tracking and avoids unnecessary data structures.