Thousand Separator - Solution & Explanation

Problem Overview: You receive a non‑negative integer n. The task is to convert it into a string where digits are grouped by thousands using a dot (.) as the separator. For example, 1234567 becomes 1.234.567. The challenge is purely formatting, but you must place separators exactly every three digits from the right side.

Approach 1: String Processing from Right to Left (O(n) time, O(n) space)

Convert the integer to a string and iterate from the last digit toward the first. Maintain a counter and insert a dot after every three digits while building the result string. Many implementations push characters into a buffer (or StringBuilder) and reverse the result at the end. The key insight: thousand separators are determined relative to the rightmost digit, so right‑to‑left iteration avoids complicated index math. This approach relies only on basic string manipulation and works consistently across languages.

The algorithm scans the digits once, making the time complexity O(n), where n is the number of digits. The output string requires O(n) extra space because separators are inserted during construction. This is the most common implementation in coding interviews because it is straightforward and language‑agnostic.

Approach 2: Using Regular Expression Formatting (O(n) time, O(n) space)

Languages with strong regular expression support can solve this with pattern-based formatting. First convert the number to a string, then apply a regex that inserts a dot before groups of three digits from the right side. Patterns typically use lookahead expressions such as (?=(\d{3})+$) to match positions where a separator should appear.

The regex engine scans the string and inserts separators automatically, producing clean and concise code. Complexity remains O(n) because the regex engine processes each digit once in typical implementations. Space complexity is also O(n) due to the newly constructed formatted string. This method is convenient in languages like Python, Java, and JavaScript where regex replacements are expressive and concise.

Recommended for interviews: The right‑to‑left string processing approach is usually expected. It shows you understand digit grouping logic and basic string processing operations without relying on language‑specific regex tricks. Regex solutions are perfectly valid in production code, but interviewers often prefer the explicit iteration because it demonstrates clear reasoning about indexing and formatting rules.