Skip to main content
DSA patterns

String to Integer (atoi)

mediumStrings Must-doMicrosoftCiscoDatadog

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

Hint 1: Treat the four steps — skip spaces, read an optional sign, read digits, clamp the range — as four separate, ordered stages rather than trying to handle everything in one pass of conditions.

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

  1. Define four states: start, sign, digits, and end, and a table saying what state each one moves to when the next character is a space, a sign, a digit, or anything else.
  2. Start in start with sign +1 and magnitude 0.
  3. For each character, look up the next state from the table. If the new state is sign, record +1 or -1. If it's digits, 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's end, stop looking at any more characters.
  4. 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"))    # -42
RecapThe 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 from digits when a . is seen (and only if a . hasn't already been consumed). While in fraction, 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 of if statements.

  • 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 (or 0, 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.