Watch 2 video solutions for Maximum Product of Two Digits, a easy level problem involving Math, Sorting. This walkthrough by Programming Live with Larry has 449 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer n.
Return the maximum product of any two digits in n.
Note: You may use the same digit twice if it appears more than once in n.
Example 1:
Input: n = 31
Output: 3
Explanation:
n are [3, 1].3 * 1 = 3.Example 2:
Input: n = 22
Output: 4
Explanation:
n are [2, 2].2 * 2 = 4.Example 3:
Input: n = 124
Output: 8
Explanation:
n are [1, 2, 4].1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8.
Constraints:
10 <= n <= 109Problem Overview: You receive an integer and need the maximum product that can be formed using any two of its digits. The task reduces to identifying the two largest digits and multiplying them.
Approach 1: Brute Force Pair Comparison (O(d²) time, O(1) space)
Extract all digits from the number, typically by repeatedly applying n % 10 and n // 10. Store them in a list and compare every possible pair of digits. For each pair, compute the product and track the maximum value found. This approach is straightforward but inefficient because it performs nested iteration across the digits. With at most 10 digits in a typical integer it still works, but interviewers expect a more optimal scan.
Approach 2: Sort Digits (O(d log d) time, O(d) space)
Extract all digits and place them in an array, then sort the array in descending order using a standard sorting algorithm. The maximum product must come from the two largest digits, which will appear at the start of the sorted list. Multiply the first two elements and return the result. Sorting simplifies the logic and works well when you already plan to process digits collectively. This approach relies on basic sorting techniques and simple math operations.
Approach 3: Track Largest and Second Largest Digits (O(d) time, O(1) space)
Scan the digits once while maintaining two variables: largest and secondLargest. For each extracted digit, update these values using simple comparisons. If the current digit exceeds largest, shift the old largest into secondLargest. If it falls between them, update only secondLargest. After processing all digits, multiply the two stored values. This single-pass strategy avoids extra memory and sorting overhead, making it the most efficient solution using only constant space and basic math operations.
Recommended for interviews: Interviewers usually expect the single-pass approach that tracks the largest and second-largest digits. Starting with the brute force idea demonstrates understanding of the problem, but recognizing that only the top two digits matter shows stronger algorithmic thinking. The O(d) scan with constant space is both clean and optimal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(d²) | O(1) | Good for demonstrating the basic idea or when digit count is extremely small |
| Sort Digits | O(d log d) | O(d) | Simple implementation when digits are already being stored or processed in arrays |
| Track Largest and Second Largest | O(d) | O(1) | Best approach for interviews and production due to single pass and constant space |