String to Integer (atoi)
Problem statement
Write a function that behaves like the classic C atoi: given a string, pull a signed integer out of the front of it, the way a config parser or a CLI flag reader would when someone might type extra spaces, a sign, or trailing junk.
The rules, in order: skip any spaces at the start; then, if the very next character is + or -, remember the sign; then read as many digits as you can find in a row; stop as soon as you hit a character that isn't a digit (or the string ends). If no digits were ever read, the answer is 0. Finally, if the number you built is too big or too small to fit in a 32-bit signed integer, clamp it to the nearest end of that range (-2^31 or 2^31 - 1) instead of overflowing.
This is the same shape of problem as safely parsing an environment variable, a --timeout=30s-style flag, or a numeric field from a log line that might have stray whitespace or garbage after it.
Examples
Example 1
Input: s = "42"
Output: 42
Explanation: No leading spaces, no sign, and every character is a digit, so the whole string becomes the number 42.
Example 2
Input: s = " -042"
Output: -42
Explanation: The leading space is skipped, the - sets the sign to negative, and the digits 042 are read as the number 42 — the leading zero doesn't add anything, so the result is -42.
Hints
Approach
Optimal: Finite-state machine
Intuition
The manual simulation above is really tracking one of a small number of "modes" at any moment: before anything meaningful, just saw the sign, reading digits, or done, ignore the rest. Writing that out as an explicit table — for each mode, what the next mode is for a space, a sign, a digit, or anything else — turns the maze of if statements into a lookup, which makes it much harder to accidentally allow something the statement doesn't (like a second sign, or digits resuming after non-digit junk).
It has the same time and space cost as the manual simulation; the benefit here is robustness and clarity rather than raw speed — if this function needed a fifth rule later (say, allowing a decimal point), you'd add one more state and a few table entries instead of untangling nested conditionals.
Steps
- Define four states:
start,sign,digits, andend, and a table saying what state each one moves to when the next character is a space, a sign, a digit, or anything else. - Start in
startwith sign+1and magnitude0. - For each character, look up the next state from the table. If the new state is
sign, record+1or-1. If it'sdigits, fold the digit into the running magnitude, capping it once it exceeds the positive 32-bit limit so it can never overflow again. If it'send, stop looking at any more characters. - Apply the sign to the final magnitude and clamp the result into
[-2^31, 2^31 - 1].
Dry run
s = "0-1"
| character | state before | state after | note |
|---|---|---|---|
'0' |
start | digits | magnitude = 0 |
'-' |
digits | end | a sign after digits isn't valid, so parsing stops here |
'1' |
end | end | never looked at — the loop stops reading once end is reached |
Result: magnitude 0, sign +1 → 0, matching the expected output. This is exactly the "stop at the first non-digit" rule from the statement, made explicit by the state table.
Edge cases: a string starting with a letter goes straight from start to end on the very first character, so the magnitude stays 0. A string of all spaces stays in start for every character and also ends with magnitude 0.
Complexity
Time O(n) - Exactly like the manual simulation, each character is looked at once as we move through the states, so the work is linear in the length of the string.
Space O(1) - A small fixed transition table plus a few variables; nothing scales with the input.
class Solution:
def myAtoi(self, s: str) -> int:
INT_MIN, INT_MAX = -2**31, 2**31 - 1
state = "start"
sign = 1
magnitude = 0
transitions = {
"start": {"space": "start", "sign": "sign", "digit": "digits", "other": "end"},
"sign": {"space": "end", "sign": "end", "digit": "digits", "other": "end"},
"digits": {"space": "end", "sign": "end", "digit": "digits", "other": "end"},
}
def char_type(ch):
if ch == ' ':
return "space"
if ch in '+-':
return "sign"
if ch.isdigit():
return "digit"
return "other"
for ch in s:
if state == "end":
break
state = transitions[state][char_type(ch)]
if state == "sign":
sign = -1 if ch == '-' else 1
elif state == "digits":
magnitude = magnitude * 10 + int(ch)
if magnitude > INT_MAX:
magnitude = INT_MAX + 1 # cap so it can never overflow again
value = sign * magnitude
return max(INT_MIN, min(INT_MAX, value))
if __name__ == "__main__":
print(Solution().myAtoi("42")) # 42
print(Solution().myAtoi(" -042")) # -42RecapThe whole problem in a few lines, for the night before
- Spot it: "parse a string into an integer" with rules about spaces, an optional sign, and clamping to a fixed range
- Idea: walk the string once — skip spaces, read an optional sign, then accumulate digits into a running total, capping it the moment it would overflow
- Cost: O(n) time, O(1) space, where n is the length of the input string
- Trap: forgetting to stop reading at the first non-digit character (don't skip over garbage looking for more digits later), and forgetting to clamp before returning rather than after an overflow already happened
Interview follow-ups
What if the input can also contain a decimal point, like "3.14"?
Add one more state,
fraction, reached fromdigitswhen a.is seen (and only if a.hasn't already been consumed). While infraction, keep reading digits into a separate fractional part instead of the integer magnitude. This changes the return type to a floating-point number and adds one transition to the table; the overall structure — states plus a transition lookup — doesn't need to change, which is the main advantage of the state-machine approach over an ad-hoc chain ofifstatements.What if leading zeros should be rejected as invalid, instead of silently ignored (so "007" is an error, not 7)?
Add a check right after the first digit is read: if that digit is
'0'and there is at least one more digit character immediately after it, treat the whole match as invalid and return an error value (or0, depending on the spec) instead of continuing to accumulate. Everything else — skipping spaces, reading the sign, clamping — stays exactly the same; only the very first digit gets this extra one-time check.
Frequently asked questions
Because the running total can be built up character by character far past what fits in a normal integer (the input allows up to 200 digits), and letting it grow unchecked can silently wrap around or waste time in languages with fixed-width integers. Capping the moment it exceeds the positive limit means every later digit is ignored for the purposes of the value, but the loop still consumes them so the index ends up in the right place — cheap and safe.
The rules say to stop reading digits at the first non-digit character, and a - sign is only recognized before any digits have been read — not in the middle. So after reading the 0, the parser is done; the -1 that follows is just unread trailing text, exactly like "4a5" would only give 4.
Turning text into a trustworthy number shows up constantly: reading a port number or timeout from an environment variable, parsing --retries=5 from a CLI flag, or pulling a numeric field out of a log line where a value like " 200" or "-1" might have stray whitespace, a sign, or garbage attached. atoi is really a stress test of whether you handle all of those cases without crashing.