LeetCode Problem 3536

Difficulty: 🟢 Easy
Topics: Math, Sorting

Solution

LeetCode 3536 - Maximum Product of Two Digits

Problem Understanding

The problem gives us a positive integer n and asks us to find the maximum product that can be formed by multiplying any two digits that appear in the number.

The input is a single integer. We must examine all of its digits and determine which pair of digits produces the largest multiplication result. The output is that maximum product.

For example, if n = 124, the digits are 1, 2, and 4. The possible products are:

• 1 × 2 = 2
• 1 × 4 = 4
• 2 × 4 = 8

The largest product is 8, so the answer is 8.

The constraint 10 <= n <= 10^9 tells us that the number contains at most 10 digits. This is a very small input size, which means even simple solutions are easily fast enough. Nevertheless, we should still think about the most direct and efficient way to solve the problem.

A few important observations and edge cases are worth noting:

• The number can contain repeated digits, such as 22.
• If the largest digit appears multiple times, we may multiply it by itself, provided it actually occurs more than once.
• Digits can include 0, which may produce products of 0.
• Since the input is at least 10, there are always at least two digits available.
• The maximum possible digit is 9, so the largest possible answer is 9 × 9 = 81.

Approaches

Brute Force

A straightforward solution is to extract all digits into an array and then examine every possible pair of digits.

For each pair (i, j) where i < j, we compute the product of the two digits and keep track of the maximum value seen so far.

This works because every valid pair is checked exactly once, guaranteeing that the largest product will be found.

Although this approach is correct, it performs unnecessary comparisons. Since the maximum product must come from the two largest digits, we can do better.

Key Insight

All digits are non-negative integers between 0 and 9.

When multiplying non-negative numbers, the largest product is always obtained by multiplying the two largest values available.

Therefore, instead of checking every pair, we can simply:

1. Extract all digits.
2. Find the two largest digits.
3. Return their product.

An easy way to do this is to sort the digits and multiply the last two elements.

Because there are at most 10 digits, sorting is effectively constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d²)	O(d)	Check every pair of digits
Optimal	O(d log d)	O(d)	Sort digits and multiply the two largest

Here, d represents the number of digits in n.

Algorithm Walkthrough

1. Convert the number into its individual digits.

We need access to every digit independently so that we can compare them and determine which are largest. 2. Store the digits in a list.

This makes it easy to sort them and access the largest values afterward. 3. Sort the digit list in ascending order.

After sorting, the two largest digits will be located at the end of the list. 4. Take the last two elements of the sorted list.

These are the largest and second-largest digits available in the number. 5. Multiply those two digits together.

Since all digits are non-negative, this product is guaranteed to be the maximum possible product of any digit pair. 6. Return the resulting product.

Why it works

Every digit is between 0 and 9, so all values are non-negative. For any set of non-negative numbers, replacing one factor with a larger value cannot decrease the product. Therefore, the largest possible product must be formed by the two largest digits in the number. Sorting allows us to identify those digits directly, and multiplying them produces the optimal answer.

Problem Understanding

This problem asks us to compute the maximum product obtainable by multiplying any two digits of a given positive integer n. The digits are extracted from n, and we are allowed to reuse the same digit twice if it appears more than once in the number. The goal is not to choose two distinct positions in the original number but rather two digits from the multiset of digits.

In other words, we first decompose n into its individual digits, then consider all possible pairs of digits (including pairing a digit with itself if it appears multiple times), and return the maximum product among all such pairs.

The input n is guaranteed to be an integer in the range 10 <= n <= 10^9, which means it has at most 10 digits. This small constraint strongly suggests that an O(d²) solution over digits would still be acceptable, but we can do better.

Key edge cases include numbers where all digits are the same, numbers where the largest digit appears only once, and numbers with a mix of small and large digits where the optimal pair may not include the first or last digit in positional order but rather the two largest digits overall.

Approaches

The brute-force approach is to extract all digits from n and try every possible pair of digits (i, j) including i == j. For each pair, we compute the product and track the maximum. This is correct because it explicitly evaluates all valid combinations. However, it is unnecessary work because we do not need all pairs to determine the maximum product.

The key insight is that the product of two numbers is maximized by using the two largest available digits. Since digits range only from 0 to 9, the problem reduces to finding the largest and second largest digits, with a special case where the largest digit appears at least twice, allowing it to be squared.

Thus, instead of comparing all pairs, we only need to identify the top two digits (or the largest digit frequency).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d²)	O(d)	Try all digit pairs explicitly
Optimal	O(d)	O(1)	Track largest and second largest digits

Here d is the number of digits in n.

Algorithm Walkthrough

The optimal solution is based on scanning the digits once and maintaining the two largest values seen so far.

1. Convert the integer n into its individual digits by repeatedly taking n % 10 and dividing n by 10. This ensures we process digits without converting to a string if we choose not to.
2. Initialize two variables first_max and second_max to track the largest and second largest digits encountered. Both start at -1 or 0 depending on implementation style.
3. For each extracted digit, compare it with first_max. If it is larger than or equal to first_max, shift the current first_max into second_max and update first_max.
4. Otherwise, if the digit is only smaller than first_max but larger than second_max, update second_max.
5. After processing all digits, compute the result as first_max * first_max if first_max appears at least twice. Otherwise compute first_max * second_max.
6. To determine whether duplication exists, we either count frequency of digits or track occurrences during scanning.

Why it works

The correctness relies on the fact that multiplication over non-negative digits is monotonically increasing with respect to both operands. Therefore, the maximum product must involve the largest possible digits. If the largest digit appears more than once, squaring it yields the maximum product. Otherwise, pairing the largest and second largest digits yields the optimal result.

Python Solution

class Solution:
    def maxProduct(self, n: int) -> int:
        digits = [int(ch) for ch in str(n)]
        digits.sort()
        return digits[-1] * digits[-2]
        digits = []
        
        # Extract digits
        while n > 0:
            digits.append(n % 10)
            n //= 10
        
        first_max = -1
        second_max = -1
        
        freq = [0] * 10
        
        # Track frequency and top two digits
        for d in digits:
            freq[d] += 1
            if d > first_max:
                second_max = first_max
                first_max = d
            elif d > second_max:
                second_max = d
        
        # If largest digit appears at least twice
        if freq[first_max] >= 2:
            return first_max * first_max
        
        return first_max * second_max

Implementation Explanation

The solution first converts the integer into a string so that each digit can be processed individually. A list comprehension converts every character back into an integer digit.

The digit list is then sorted in ascending order. After sorting, the largest digit is stored at digits[-1] and the second-largest digit is stored at digits[-2].

Multiplying these two values gives the maximum possible product, which is returned immediately. The code first extracts all digits from n into a list. It then maintains both frequency information and the two largest digits in a single pass over the digits.

The freq array is used to detect whether the largest digit appears more than once, which is necessary to determine whether squaring it is valid. Meanwhile, first_max and second_max are updated dynamically to always represent the two largest distinct digits seen so far.

Finally, the function returns either the square of the largest digit or the product of the two largest digits depending on frequency.

Go Solution

import "sort"

func maxProduct(n int) int {
    digits := []int{}

    for n > 0 {
        digits = append(digits, n%10)
        n /= 10
    }

    sort.Ints(digits)

    m := len(digits)
    return digits[m-1] * digits[m-2]
}

Go-Specific Notes

The Go solution extracts digits using repeated modulo and division operations rather than converting the number to a string.

The digits are stored in a slice and sorted using sort.Ints. After sorting, the last two elements contain the largest digits, and their product is returned.

Integer overflow is not a concern because the largest possible result is 81. func maxProduct(n int) int { freq := make([]int, 10)

firstMax := -1
secondMax := -1

for n > 0 {
    digit := n % 10
    n /= 10

    freq[digit]++

    if digit > firstMax {
        secondMax = firstMax
        firstMax = digit
    } else if digit > secondMax {
        secondMax = digit
    }
}

if freq[firstMax] >= 2 {
    return firstMax * firstMax
}

return firstMax * secondMax

}

### Go-specific Notes

The Go implementation mirrors the Python logic closely. Slices are used for digit frequency tracking since Go does not have built-in fixed-size arrays with zero initialization semantics as concisely as Python lists in this context. Integer arithmetic is safe because digit values are small and the result fits within standard integer bounds.

Unlike Python, Go requires explicit initialization of slices using `make`. The rest of the logic remains identical, and no special handling for overflow is needed because the maximum product is `9 * 9 = 81`.

## Worked Examples

### Example 1: n = 31

Digits extracted:

| Step | Digits |
| --- | --- |
| Initial | [3, 1] |
| After sort | [1, 3] |

Final calculation:

| Largest | Second Largest | Product |
| --- | --- | --- |
| 3 | 1 | 3 |

Answer: `3`

### Example 2: n = 22

Digits extracted:

| Step | Digits |
| --- | --- |
| Initial | [2, 2] |
| After sort | [2, 2] |

Final calculation:

| Largest | Second Largest | Product |
| --- | --- | --- |
| 2 | 2 | 4 |

Answer: `4`

### Example 3: n = 124

Digits extracted:

| Step | Digits |
| --- | --- |
| Initial | [1, 2, 4] |
| After sort | [1, 2, 4] |

Final calculation:

| Largest | Second Largest | Product |
| --- | --- | --- |
| 4 | 2 | 8 |

Answer: `8`
Digits extracted: `[3, 1]`

| Step | Digit | first_max | second_max | freq |
| --- | --- | --- | --- | --- |
| 1 | 3 | 3 | -1 | 3:1 |
| 2 | 1 | 3 | 1 | 1:1 |

Final check: `freq[3] = 1`, so no duplication.

Result: `3 * 1 = 3`

### Example 2: n = 22

Digits extracted: `[2, 2]`

| Step | Digit | first_max | second_max | freq |
| --- | --- | --- | --- | --- |
| 1 | 2 | 2 | -1 | 2:1 |
| 2 | 2 | 2 | 2 | 2:2 |

Final check: `freq[2] = 2`, so duplication exists.

Result: `2 * 2 = 4`

### Example 3: n = 124

Digits extracted: `[1, 2, 4]`

| Step | Digit | first_max | second_max | freq |
| --- | --- | --- | --- | --- |
| 1 | 1 | 1 | -1 | 1:1 |
| 2 | 2 | 2 | 1 | 2:1 |
| 3 | 4 | 4 | 2 | 4:1 |

Final check: `freq[4] = 1`

Result: `4 * 2 = 8`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(d log d) | Sorting the digits dominates the runtime |
| Space | O(d) | Storage for the digit list |

Since `d` is the number of digits in `n`, and `n ≤ 10^9`, we have at most 10 digits. In practice, the runtime and memory usage are extremely small. The asymptotic complexity comes from the sorting operation.
| Time | O(d) | Each digit is processed once |
| Space | O(1) | Frequency array size is fixed at 10 |

The algorithm is linear in the number of digits of `n`, which is bounded by 10. Therefore, it is effectively constant time in practice.

## Test Cases

sol = Solution()

assert sol.maxProduct(31) == 3 # example 1 assert sol.maxProduct(22) == 4 # example 2 assert sol.maxProduct(124) == 8 # example 3

assert sol.maxProduct(10) == 0 # minimum value containing zero assert sol.maxProduct(99) == 81 # largest possible product assert sol.maxProduct(909) == 81 # repeated largest digit assert sol.maxProduct(123456789) == 72 # 9 * 8 assert sol.maxProduct(1000000000) == 0 # one nonzero digit and many zeros assert sol.maxProduct(777777) == 49 # all digits identical assert sol.maxProduct(9831) == 72 # largest two digits are 9 and 8 assert sol.maxProduct(5551) == 25 # repeated maximum digit

provided examples

assert Solution().maxProduct(31) == 3 # basic two-digit case assert Solution().maxProduct(22) == 4 # duplicate digit allows squaring assert Solution().maxProduct(124) == 8 # general case with max pair

edge cases

assert Solution().maxProduct(10) == 0 # includes zero digit assert Solution().maxProduct(99) == 81 # all digits same and repeated assert Solution().maxProduct(91) == 9 # largest and smallest digit assert Solution().maxProduct(109) == 9 # zero should not affect max

### Test Summary

| Test | Why |
| --- | --- |
| `31` | Basic two-digit input |
| `22` | Repeated digit case |
| `124` | Standard multi-digit example |
| `10` | Includes zero |
| `99` | Maximum possible answer |
| `909` | Largest digit appears twice |
| `123456789` | Many distinct digits |
| `1000000000` | Mostly zeros |
| `777777` | All digits identical |
| `9831` | Largest two digits are not adjacent in the original number |
| `5551` | Repeated maximum digit |

## Edge Cases

### Numbers Containing Zero

A common source of bugs is assuming every digit contributes positively to the product. For example, `n = 10` contains digits `1` and `0`, producing a product of `0`. The implementation naturally handles this because sorting places `0` among the digits and multiplication works normally.

### Repeated Largest Digit

Consider `n = 22` or `n = 909`. The optimal product uses the same digit value twice because that digit appears multiple times in the number. Sorting preserves all occurrences, so the two largest elements are correctly selected even when they are equal.

### All Digits Identical

For inputs such as `777777`, every digit is the same. Some implementations might overcomplicate pair selection, but this approach simply sorts the digits and multiplies the last two values. The result is correctly computed as `7 × 7 = 49`.

### Large Input Near the Constraint Limit

For `n = 1000000000`, the number contains ten digits, which is the maximum possible under the constraints. The algorithm still processes only a tiny number of digits and correctly returns `0` because the two largest digits are `1` and `0`. The runtime remains effectively constant.
| 31 | simple distinct digits |
| 22 | repeated digit case |
| 124 | normal multi-digit ordering |
| 10 | zero handling |
| 99 | identical digits |
| 91 | descending digits |
| 109 | zero mixed with large digit |

## Edge Cases

One important edge case is when the number contains the digit zero. Since zero is a valid digit but produces zero product with any number, it should never influence the maximum unless all other digits are also zero or one.

Another edge case occurs when all digits are identical, such as `99` or `111`. In this case, the correct result is the square of that digit, and the algorithm must correctly detect frequency rather than relying solely on distinct ordering.

A third edge case is when the largest digit appears only once. In this case, we must ensure the algorithm correctly falls back to the second largest digit rather than mistakenly attempting to square the largest digit.

All these cases are correctly handled through the combination of frequency tracking and maintaining the top two digits during a single traversal.