Integer to English Words (LeetCode 273): Clean Decomposition Under Pressure
6 views
Convert a non-negative integer up to 2^31 - 1 into English words. 123 becomes "One Hundred Twenty Three", 12345 becomes "Twelve Thousand Three Hundred Forty Five", and 1000010 becomes "One Million Ten". There is no clever algorithm here; the interview is about decomposition, edge cases and clean code.
Step 1: Notice the structure
English names numbers in groups of three digits: units, thousands, millions, billions. Each group is read the same way ("three hundred forty five") and then followed by its scale word. So the problem reduces to:
1. Write a helper that converts 0 to 999.
2. Split the number into three-digit chunks and attach scale words.
Step 2: The lookup tables
below_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
"Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty",
"Seventy", "Eighty", "Ninety"]
scales = ["", "Thousand", "Million", "Billion"]
Numbers below 20 are irregular, which is why they get their own table.
Step 3: The code
def number_to_words(num):
if num == 0:
return "Zero"
def three(n):
words = []
if n >= 100:
words += [below_20[n // 100], "Hundred"]
n %= 100
if n >= 20:
words.append(tens[n // 10])
n %= 10
if n > 0:
words.append(below_20[n])
return words
result, i = [], 0
while num > 0:
chunk = num % 1000
if chunk:
result = three(chunk) + ([scales[i]] if scales[i] else []) + result
num //= 1000
i += 1
return " ".join(result)
Building a list of words and joining once avoids the classic double-space and trailing-space bugs.
Edge cases interviewers check
- 0 must return "Zero"; the helper alone returns nothing.
- Empty chunks: 1000010 has a zero thousands chunk, so "Thousand" must not appear.
- Teens: 15 is "Fifteen", not "Ten Five".
- Exact tens: 40 is "Forty", with nothing after it.
- The maximum value, 2147483647, exercises every scale.
Complexity
The number of chunks is constant (at most four), so time and space are O(1) for 32-bit input, or O(log n) in general.
Follow-ups
- British style with "and" ("one hundred and five").
- Ordinals ("twenty-first").
- Reverse direction: parse English words back into an integer, which tests the same decomposition in reverse.
How to present it
Explain the three-digit grouping idea first, write the helper, then the loop, and trace 1000010 out loud. Under pressure it is easy to forget the empty-chunk rule; Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly surfacing reminders like that while you explain your solution in your own words.