LeetCode 1556 - Thousand Separator

LeetCode Problem 1556

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to format a non-negative integer so that every group of three digits is separated by a dot (.), starting from the right side of the number.

For example, the number 1234567 should become "1.234.567" because the digits are grouped as:

• 1
• 234
• 567

The input is a single integer n, and the output must be a string representation of that integer with the appropriate separators inserted.

The constraints are small:

• 0 <= n <= 2^31 - 1

This tells us several important things:

• The input always fits inside a standard 32-bit signed integer.
• The maximum number has at most 10 digits.
• Performance is not a concern because the input size is tiny.
• A straightforward string-based solution is perfectly acceptable.

There are several important edge cases to consider.

The first edge case is 0. A careless implementation might return an empty string if it processes digits in groups incorrectly. The correct answer is simply "0".

Another edge case is when the number has fewer than four digits, such as 7 or 987. These numbers should not contain any dots because they do not have a thousands group.

We also need to correctly handle numbers whose digit count is not a multiple of three. For example:

• 1234 becomes "1.234"
• 12345 becomes "12.345"

The leftmost group may contain one or two digits, while all remaining groups contain exactly three digits.

Approaches

Brute Force Approach

A brute-force style solution would repeatedly extract digits from the number using modulo and division operations.

The idea is:

1. Repeatedly take the last digit using n % 10
2. Build groups of three digits
3. Insert dots between groups
4. Reverse the final result because digits are extracted from right to left

This approach works because every decimal digit can be processed individually, and grouping digits in chunks of three naturally matches the formatting requirement.

However, this method is unnecessarily complicated for this problem. Managing digit groups manually introduces additional bookkeeping, including:

• Counting digits
• Handling partial groups
• Reversing intermediate strings
• Carefully placing separators

Even though the constraints are tiny and the approach is still fast enough, it is more error-prone than necessary.

Optimal Approach

The key observation is that the number can first be converted into a string. Once we have the string form, the problem becomes simple string formatting.

We process the digits from right to left in chunks of three characters. Every time we collect three digits, we insert a dot before the next group.

This works well because:

• String slicing is straightforward
• Groups of three are naturally represented as substrings
• We avoid manual digit extraction and reversal complexity

The algorithm is simple, readable, and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Extracts digits one by one using modulo and division
Optimal	O(d)	O(d)	Uses string slicing and grouping from the right

Here, d represents the number of digits in the integer.

Algorithm Walkthrough

1. Convert the integer n into a string.

This allows us to work directly with digit characters instead of repeatedly using arithmetic operations. String manipulation is simpler and less error-prone for formatting problems. 2. Create an empty list to store digit groups.

Each group will contain at most three digits. Using a list is efficient because appending groups is fast. 3. Start from the end of the string and move left in steps of three.

Since thousands separators are inserted every three digits from the right side, processing from right to left naturally matches the formatting rule. 4. Extract substrings of length three.

For each iteration:

• Take the substring from max(0, i - 3) to i
• Append that substring to the groups list

The leftmost group may contain fewer than three digits, which is handled automatically by the slice boundaries. 5. Reverse the groups list.

Because groups were collected from right to left, reversing restores the correct left-to-right order. 6. Join all groups using ".".

This produces the final formatted string.

Why it works

The algorithm works because decimal numbers are grouped into blocks of three digits starting from the rightmost digit. By iterating from the end of the string in steps of three, every extracted substring corresponds exactly to one valid thousands group. Reversing the collected groups restores the original order, and joining them with dots produces the required format.

Python Solution

class Solution:
    def thousandSeparator(self, n: int) -> str:
        digits = str(n)
        groups = []

        for i in range(len(digits), 0, -3):
            start = max(0, i - 3)
            groups.append(digits[start:i])

        groups.reverse()

        return ".".join(groups)

The implementation begins by converting the integer into a string called digits. This makes it easy to slice groups of characters directly.

The groups list stores chunks of up to three digits. The loop starts at the end of the string and moves backward by three positions at a time.

For every iteration:

• start marks the beginning of the current group
• digits[start:i] extracts the substring
• The substring is appended to groups

Because groups are collected from right to left, the list is reversed afterward.

Finally, ".".join(groups) combines all groups into the required formatted string.

Go Solution

package main

import (
	"strings"
)

func thousandSeparator(n int) string {
	digits := []byte(string(rune(n + '0')))

	if n >= 10 {
		digits = []byte{}
		numStr := strconv.Itoa(n)

		for i := len(numStr); i > 0; i -= 3 {
			start := i - 3
			if start < 0 {
				start = 0
			}

			digits = append([]byte(numStr[start:i]), append([]byte("."), digits...)...)
		}

		if digits[0] == '.' {
			digits = digits[1:]
		}

		return string(digits)
	}

	return string(digits)
}

A cleaner and more idiomatic Go implementation is shown below.

package main

import (
	"strconv"
	"strings"
)

func thousandSeparator(n int) string {
	numStr := strconv.Itoa(n)
	groups := []string{}

	for i := len(numStr); i > 0; i -= 3 {
		start := i - 3
		if start < 0 {
			start = 0
		}

		groups = append(groups, numStr[start:i])
	}

	for left, right := 0, len(groups)-1; left < right; left, right = left+1, right-1 {
		groups[left], groups[right] = groups[right], groups[left]
	}

	return strings.Join(groups, ".")
}

The Go version follows the same logic as the Python implementation.

Some Go-specific details are worth noting:

• strconv.Itoa converts the integer into a string.
• Slices of strings are stored in groups.
• Go does not provide a built-in reverse function for slices, so we manually swap elements using two pointers.
• strings.Join combines the groups using ".".

Because the constraints are small, there is no concern about memory usage or overflow during formatting.

Worked Examples

Example 1

Input:

n = 987

Initial string:

"987"

Iteration	i	Extracted Group	groups
1	3	"987"	["987"]

After reversing:

["987"]

Joined result:

"987"

Final output:

"987"

Example 2

Input:

n = 1234

Initial string:

"1234"

Iteration	i	Extracted Group	groups
1	4	"234"	["234"]
2	1	"1"	["234", "1"]

After reversing:

["1", "234"]

Joined result:

"1.234"

Final output:

"1.234"

Additional Example

Input:

n = 123456789

Initial string:

"123456789"

Iteration	i	Extracted Group	groups
1	9	"789"	["789"]
2	6	"456"	["789", "456"]
3	3	"123"	["789", "456", "123"]

After reversing:

["123", "456", "789"]

Joined result:

"123.456.789"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is processed once
Space	O(d)	Additional storage is used for groups and the final string

Here, d is the number of digits in the integer.

The algorithm scans the string representation exactly once in chunks of three characters. All slicing and joining operations together still process each digit only once overall. The auxiliary list storing groups also requires linear space relative to the number of digits.

Test Cases

solution = Solution()

assert solution.thousandSeparator(987) == "987"  # No separator needed
assert solution.thousandSeparator(1234) == "1.234"  # Single separator
assert solution.thousandSeparator(1234567) == "1.234.567"  # Multiple separators
assert solution.thousandSeparator(0) == "0"  # Zero edge case
assert solution.thousandSeparator(1) == "1"  # Single digit
assert solution.thousandSeparator(12) == "12"  # Two digits
assert solution.thousandSeparator(999) == "999"  # Exactly three digits
assert solution.thousandSeparator(1000) == "1.000"  # Boundary crossing
assert solution.thousandSeparator(1000000) == "1.000.000"  # Large grouped number
assert solution.thousandSeparator(2147483647) == "2.147.483.647"  # Maximum constraint value

Test	Why
987	Verifies no separator for fewer than four digits
1234	Verifies one separator insertion
1234567	Verifies multiple separator insertions
0	Validates zero handling
1	Validates smallest positive number
12	Validates two-digit input
999	Validates exactly three digits
1000	Verifies transition into thousands
1000000	Verifies repeated grouping
2147483647	Tests maximum allowed input

Edge Cases

One important edge case is the value 0. Some implementations that repeatedly divide the number by ten may accidentally skip processing entirely and return an empty string. In this implementation, converting the integer to a string immediately guarantees that "0" is processed correctly.

Another important edge case is numbers with exactly three digits, such as 999. A buggy implementation might incorrectly insert a leading separator and produce ".999". Since the algorithm only inserts separators between groups after grouping is complete, no unnecessary separator appears.

A third edge case is numbers whose digit count is not divisible by three, such as 12345. The leftmost group contains only two digits, while all other groups contain three. The slicing logic naturally handles this by using max(0, i - 3) for the group boundary, ensuring the first group can be shorter without special-case logic.

A final edge case is the maximum allowed value, 2147483647. This verifies that the implementation correctly handles multiple separators and larger digit counts without overflow or formatting errors. Since the algorithm operates on strings, integer size does not create additional complications once conversion is complete.