Python 1796.py
class Solution:
def secondHighest(self, s: str) -> int:
digits = set()
for c in s:
if "0" <= c <= "9":
digits.add(int(c))
return sorted(digits)[-2] if len(digits) >= 2 else -1
Difficulty
and has an acceptance rate of about 55% (200k+ submissions).
Typical patterns to solve this problem:
- Hash Table
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a single method secondHighest. The method receives a string, extracts all numeric characters, and returns the second largest distinct digit found in the string. If fewer than two distinct digits exist, the method returns -1. The algorithm is concise, leverages Python’s built-in data structures, and operates directly on the input without auxiliary preprocessing.
Key Steps
The core logic can be broken down into three conceptual stages: collection, conversion, and selection. Each stage is illustrated with the corresponding fragment of the original source.
Collection of Digits
The method begins by creating an empty set named digits. A set is chosen because it automatically discards duplicate values, ensuring that each digit is stored only once.
digits = set()
Scanning and Filtering
A for loop iterates over every character c in the input string s. The conditional expression "0" <= c <= "9" checks whether the character falls within the ASCII range for decimal digits. When the condition holds, the character is converted to an integer and added to the digits set.
for c in s:
if "0" <= c <= "9":
digits.add(int(c))
Determining the Second Highest Value
After the scan completes, the set contains all distinct numeric characters present in the string. The set is transformed into a sorted list, which orders the digits in ascending order. The expression sorted(digits)[-2] accesses the element positioned second from the end, i.e., the second largest digit. A ternary conditional guards this operation: if the set holds at least two elements, the second highest digit is returned; otherwise, -1 signals the absence of a qualifying value.
return sorted(digits)[-2] if len(digits) >= 2 else -1
Edge Cases Handled
The implementation gracefully addresses several boundary conditions without additional code. When the input string contains no numeric characters, the digits set remains empty; the length check fails, and the method returns -1. If the string includes exactly one distinct digit-regardless of how many times it appears-the length condition again fails, yielding -1. Repeated occurrences of the same digit are collapsed by the set, preventing false positives for a second highest value. Non-digit characters, including letters, symbols, and whitespace, are ignored by the range check, ensuring they never affect the result. Leading zeros are treated as the integer 0, which participates correctly in the ordering logic; for example, a string "a0b0c" still yields -1 because only one distinct digit exists.
Performance Optimizations
The algorithm exploits the limited domain of possible digits (0-9) to keep work minimal. By storing digits in a set, the code eliminates duplicate processing early, reducing the size of the collection that later requires sorting. Since the maximum cardinality of the set is ten, the subsequent sorted call operates on a tiny, bounded list, making the sorting step effectively constant-time in practice. Leveraging Python’s built-in comparison operators for the range check ("0" <= c <= "9") avoids the overhead of regular expression matching or explicit conversion attempts, resulting in a fast, linear scan of the input string. The overall flow processes each character exactly once, and the use of native data structures ensures that the interpreter can apply highly optimized C-level implementations for set insertion and sorting.
ELI5 - Simplified Explanation
Imagine there is a big basket that starts out completely empty. A tiny robot looks at every single letter and number inside a long line of text. When the robot sees a digit like one, two, or three, it picks it up and puts it into the basket. The basket is special because it only allows one of each number, so if the robot finds two fives, it only keeps one of them. Once the robot looks at every single character in the message, it lines all the numbers it found up in order from the smallest to the largest, just like building a tall tower with blocks. After the tower is built, it looks for the second block from the top and holds that one up to show everyone. If there are not enough blocks in the tower to find a second one from the top, it lets everyone know that it could not find a winner.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | Java | C | Go | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C, C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| lkwq007 | Python | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 2259: Remove Digit From Number to Maximize Result
Solved On The Same Day
- problem 1128: Number of Equivalent Domino Pairs
- problem 2413: Smallest Even Multiple
- problem 2609: Find the Longest Balanced Substring of a Binary String
- problem 2748: Number of Beautiful Pairs
- problem 2798: Number of Employees Who Met the Target
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality