LeetCode 1323 - Maximum 69 Number

LeetCode Problem 1323

Difficulty: 🟢 Easy
Topics: Math, Greedy

Solution

Problem Understanding

The problem gives us a positive integer num that contains only the digits 6 and 9. We are allowed to change at most one digit, where a 6 can become a 9, or a 9 can become a 6. Our goal is to return the largest possible number after making zero or one modification.

In simpler terms, we want to maximize the number by strategically choosing whether to flip one digit. Since the digits are restricted to only 6 and 9, the decision becomes straightforward: changing a 6 into a 9 increases the value, while changing a 9 into a 6 decreases it. Therefore, any useful change must involve converting a 6 into a 9.

The position of the digit matters because numbers are positional. A digit near the front contributes more to the total value than a digit near the end. For example, changing the leftmost 6 in 9669 increases the thousands place, which has a much greater impact than changing a later digit.

The constraints are very small:

• 1 <= num <= 10^4
• num contains only digits 6 and 9

This tells us that the number has at most 5 digits, so even inefficient solutions would work within limits. However, the goal in interview and algorithmic settings is to identify the most elegant and optimal approach.

There are several important edge cases to consider:

• The number may already consist entirely of 9s, such as 9999. In this case, any change would reduce the number, so the correct answer is to make no change.
• The number may contain only one digit, such as 6 or 9.
• Multiple 6s may exist, but only one digit can be changed. Since earlier digits matter more, changing the first 6 from the left is always optimal.
• The problem guarantees the input contains only 6 and 9, so we do not need extra validation for other digits.

Approaches

Brute Force Approach

A brute-force solution would try changing every digit one at a time and compute the resulting number. For each position, we would flip the digit (6 ↔ 9) and keep track of the maximum value obtained.

For example, with 9669, we could generate:

• Change index 0: 6669
• Change index 1: 9969
• Change index 2: 9699
• Change index 3: 9666

We would also consider making no change at all. The largest value among all possibilities is the answer.

This approach is correct because it exhaustively checks every valid modification. However, it performs unnecessary work because we can reason mathematically about which modification is best.

Optimal Greedy Approach

The key insight is that changing a 6 to a 9 always increases the number, while changing a 9 to a 6 always decreases it. Therefore, we should never change a 9.

The next observation is that earlier digits matter more than later digits because of place value. A change in the thousands place is more valuable than a change in the tens place.

This means the best strategy is simple:

1. Scan the number from left to right.
2. Find the first 6.
3. Change it to 9.
4. Return the result immediately.

If no 6 exists, the number is already maximal.

This is a greedy strategy because we make the locally best choice, changing the most significant 6, and that decision guarantees the globally optimal result.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d²)	O(d)	Try flipping every digit and compute the maximum result
Optimal	O(d)	O(d)	Change the first 6 to 9 and stop

Here, d represents the number of digits in num.

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Convert the integer into a string or list of characters so individual digits can be modified easily. Since integers are immutable at the digit level, working with strings simplifies manipulation.
2. Traverse the digits from left to right. We scan in this direction because earlier digits contribute more to the overall number value.
3. Check whether the current digit is 6. The first 6 encountered is the most valuable position to modify.
4. If a 6 is found, replace it with 9. Since only one change is allowed, stop searching immediately.
5. Convert the modified digit sequence back into an integer and return it.
6. If no 6 exists after the scan completes, return the original number unchanged because it is already the maximum possible value.

Why it works

The correctness relies on positional value. Changing a 6 to a 9 increases the number by an amount proportional to its place value. A 6 in a more significant position contributes more than one in a less significant position. Therefore, modifying the leftmost 6 produces the largest possible increase. Since changing any 9 decreases the number, and only one change is allowed, this greedy choice is always optimal.

Python Solution

class Solution:
    def maximum69Number(self, num: int) -> int:
        digits = list(str(num))

        for index in range(len(digits)):
            if digits[index] == "6":
                digits[index] = "9"
                break

        return int("".join(digits))

The implementation starts by converting the integer into a list of characters. This allows us to modify a digit directly, since strings are immutable in Python.

We then iterate through the digits from left to right. As soon as we encounter the first 6, we replace it with 9 and immediately stop the loop using break. Stopping early is important because only one modification is allowed, and the first 6 gives the maximum gain.

Finally, we join the modified digits back into a string and convert it to an integer before returning the result.

Go Solution

func maximum69Number(num int) int {
	digits := []byte(fmt.Sprintf("%d", num))

	for i := 0; i < len(digits); i++ {
		if digits[i] == '6' {
			digits[i] = '9'
			break
		}
	}

	result := 0
	for _, digit := range digits {
		result = result*10 + int(digit-'0')
	}

	return result
}

The Go implementation follows the same greedy logic as the Python solution. Since Go strings are immutable, we convert the number into a byte slice for in-place modification.

One implementation detail is that Go requires explicit integer reconstruction. After modifying the digits, we rebuild the integer manually by iterating through the byte slice and applying base-10 accumulation.

Unlike Python, there is no need to worry about integer overflow here because the maximum input is only 10^4.

Worked Examples

Example 1

Input: num = 9669

Initial digits:

Index	Digit
0	9
1	6
2	6
3	9

Step-by-step execution:

Step	Index	Digit	Action	Result
1	0	9	Skip	9669
2	1	6	Change to 9	9969
3	-	-	Stop scanning	9969

Final answer: 9969

Example 2

Input: num = 9996

Initial digits:

Index	Digit
0	9
1	9
2	9
3	6

Step-by-step execution:

Step	Index	Digit	Action	Result
1	0	9	Skip	9996
2	1	9	Skip	9996
3	2	9	Skip	9996
4	3	6	Change to 9	9999

Final answer: 9999

Example 3

Input: num = 9999

Initial digits:

Index	Digit
0	9
1	9
2	9
3	9

Step-by-step execution:

Step	Index	Digit	Action	Result
1	0	9	Skip	9999
2	1	9	Skip	9999
3	2	9	Skip	9999
4	3	9	Skip	9999

No 6 is found, so the number remains unchanged.

Final answer: 9999

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	We scan the digits at most once
Space	O(d)	We store the digits as a mutable string/list

Here, d is the number of digits in num.

The algorithm performs a single pass through the number, stopping as soon as the first 6 is found. In the worst case, such as 9999, every digit is checked once. The extra space comes from storing the number as a character list or byte slice for modification.

Test Cases

solution = Solution()

assert solution.maximum69Number(9669) == 9969  # Example case, first 6 changes
assert solution.maximum69Number(9996) == 9999  # Example case, last digit changes
assert solution.maximum69Number(9999) == 9999  # No change needed

assert solution.maximum69Number(6) == 9  # Single digit 6
assert solution.maximum69Number(9) == 9  # Single digit 9

assert solution.maximum69Number(6699) == 9699  # Change leftmost 6
assert solution.maximum69Number(6969) == 9969  # First 6 gives max gain
assert solution.maximum69Number(6666) == 9666  # Only one change allowed

assert solution.maximum69Number(6966) == 9966  # Multiple 6s, choose first
assert solution.maximum69Number(9696) == 9996  # Last 6 changes

Test	Why
9669 → 9969	Validates the first example
9996 → 9999	Validates modifying the last digit
9999 → 9999	Confirms no change when already maximal
6 → 9	Tests smallest input with improvement
9 → 9	Tests smallest input with no change
6699 → 9699	Ensures leftmost 6 is chosen
6969 → 9969	Confirms greedy selection
6666 → 9666	Verifies only one modification
6966 → 9966	Multiple candidate positions
9696 → 9996	Tests later-position replacement

Edge Cases

One important edge case is when the number already contains only 9s, such as 9999. A careless implementation might always force a digit flip and accidentally reduce the value to something smaller. Our implementation handles this correctly because it only modifies a digit if it finds a 6. If none exists, the original number is returned unchanged.

Another important case is a single-digit input such as 6 or 9. Since there is only one digit, the algorithm must still behave correctly without relying on multiple iterations. For 6, it changes directly to 9. For 9, no change is made.

A third edge case occurs when multiple 6s are present, such as 6666. A naive implementation might attempt to change all 6s or choose the wrong one. Our greedy logic correctly changes only the first 6, because it has the highest positional value and produces the maximum possible increase.

Finally, consider cases where the only 6 appears near the end, such as 9996. The algorithm scans through all leading 9s and eventually updates the last digit. This confirms the solution handles both early and late modifications correctly.