Log inSign up
mediumleetcodeNot Started

String to Integer (atoi)

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace. 2. Check if the next character is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. 3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. 4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary. 5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1. 6. Return the integer as the final result.

Example 1:

Input: s = "42"
Output: 42
Explanation: The parsed integer is 42.

Example 2:

Input: s = " -042"
Output: -42
Explanation: Leading whitespace skipped, sign is negative, leading zeros stripped -> -42.

Example 3:

Input: s = "1337c0d3"
Output: 1337
Explanation: Conversion stops at c -> 1337.

Example 4:

Input: s = "0-1"
Output: 0
Explanation: Conversion reads 0 and stops at - -> 0.

Example 5:

Input: s = "words and 987"
Output: 0
Explanation: First non-whitespace character is w, no valid digits read -> 0.

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Safely detect 32-bit signed integer overflow before multiplication.
  • Handle multi-phase string parsing with early termination.
  • Normalize negative and positive sign edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Parsing numbers from raw formatted text with strict boundary clipping.
  • Emulating low-level standard library conversion routines.

Algorithmic Decision Tree:

  • Parsing numbers from raw formatted text with strict boundary clipping.
  • Emulating low-level standard library conversion routines.

Connected Patterns:

String CompressionValid NumberReverse Integer

1. 64-bit Integer Accumulator

Intuition

Skip whitespace. Check sign. Accumulate digits into a 64-bit long long integer. If the accumulated value with sign exceeds INT_MAX (2147483647), clamp to INT_MAX. If it falls below INT_MIN (-2147483648), clamp to INT_MIN.

When to apply: When 64-bit integers are permitted and simplicity is preferred.

Algorithm

  1. Initialize i = 0, sign = 1, total = 0.
  2. While i < n && s[i] == ' ': i++.
  3. If i < n && (s[i] == '+' || s[i] == '-'): sign = (s[i] == '-') ? -1 : 1; i++.
  4. While i < n && isDigit(s[i]):
  5. total = total * 10 + (s[i] - '0')
  6. If sign * total > 2147483647: return 2147483647.
  7. If sign * total < -2147483648: return -2147483648.
  8. i++.
  9. Return sign * total.

64-bit Integer Accumulator

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 1, 9, 3, , w, i, t, h, ]
Current operationSTEP 1 OF 6
Observation: String starts immediately with digit '4' (no leading spaces or sign)
Visual state
Values and pointers at this exact step
array
S
4
1
9
3
w
i
t
h
0
↑ FIRST CHAR: '4'
1
2
3
4
5
6
7
8
9
Variables at this step
idx
0
sign
1
num
4
Check / comparison
Scan leading characters: no spaces, no '+' or '-' sign. Sign = +1.
Decision / next transition
Char '4' is a digit. Initialize num = 4.
Why this step matters

Observation: String starts immediately with digit '4' (no leading spaces or sign).

Decision: Sign is +1. Start numerical accumulator: num = 4.

Invariant: Whitespace trimming and sign detection must precede digit parsing.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <climits>
4
5class Solution {
6public:
7 int myAtoi(std::string s) {
8 int i = 0, n = s.size();
9 while (i < n && s[i] == ' ') i++;
10 if (i == n) return 0;
11
12 int sign = 1;
13 if (s[i] == '+' || s[i] == '-') {
14 sign = (s[i] == '-') ? -1 : 1;
15 i++;
16 }
17
18 long long total = 0;
19 while (i < n && isdigit(s[i])) {
20 total = total * 10 + (s[i] - '0');
21 if (sign == 1 && total > INT_MAX) return INT_MAX;
22 if (sign == -1 && -total < INT_MIN) return INT_MIN;
23 i++;
24 }
25
26 return sign * total;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::cout << sol.myAtoi("42") << std::endl; // 42
33 std::cout << sol.myAtoi(" -042") << std::endl; // -42
34 std::cout << sol.myAtoi("1337c0d3") << std::endl; // 1337
35 std::cout << sol.myAtoi("-91283472332") << std::endl; // -2147483648
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass over characters in string.
  • Space complexity: O(1)

Why Brute Force Doesn't Scale:

Single linear pass with proactive threshold checking eliminates 64-bit casting.

Zero memory allocations; runs strictly in registers.

2. Deterministic Finite Automaton (DFA)

Intuition

Define states START (0), SIGNED (1), IN_NUM (2), DEAD (3). Transitions are governed by character type (space, sign, digit, other). In IN_NUM, accumulate digits and check overflow. Any invalid character transitions to DEAD.

When to apply: When formal state transition parsing is requested.

Algorithm

  1. Initialize state = 0, sign = 1, res = 0.
  2. For each character in s:
  3. Map character to input group (space=0, sign=1, digit=2, other=3).
  4. Transition state based on DFA matrix.
  5. If state == IN_NUM: accumulate digit and check overflow.
  6. If state == DEAD: break.
  7. Return sign * res.

Deterministic Finite Automaton (DFA)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 1, 9, 3, , w, i, t, h, ]
Current operationSTEP 1 OF 6
Observation: DFA states: START (0), SIGNED (1), IN_NUMBER (2), END (3)
Visual state
Values and pointers at this exact step
array
S
4
1
9
3
w
i
t
h
0
↑ DFA: START -> IN_NUM
1
2
3
4
5
6
7
8
9
Variables at this step
state
IN_NUMBER
total
4
sign
1
Check / comparison
State START (0). Input '4' is digit. Transition to State IN_NUM (2).
Decision / next transition
total = 4, sign = +1.
Why this step matters

Observation: DFA states: START (0), SIGNED (1), IN_NUMBER (2), END (3).

Decision: Input '4' transitions directly from START to IN_NUMBER. Set total = 4.

Invariant: DFA formally models state machine transitions without nested flag logic.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <climits>
5
6class Solution {
7public:
8 int myAtoi(std::string s) {
9 // State 0: START, 1: SIGNED, 2: IN_NUM, 3: DEAD
10 int state = 0, sign = 1;
11 long long res = 0;
12
13 for (char c : s) {
14 int inputType = 3;
15 if (c == ' ') inputType = 0;
16 else if (c == '+' || c == '-') inputType = 1;
17 else if (isdigit(c)) inputType = 2;
18
19 if (state == 0) {
20 if (inputType == 0) continue;
21 else if (inputType == 1) { state = 1; sign = (c == '-') ? -1 : 1; }
22 else if (inputType == 2) { state = 2; res = c - '0'; }
23 else break;
24 } else if (state == 1) {
25 if (inputType == 2) { state = 2; res = c - '0'; }
26 else break;
27 } else if (state == 2) {
28 if (inputType == 2) {
29 res = res * 10 + (c - '0');
30 if (sign == 1 && res > INT_MAX) return INT_MAX;
31 if (sign == -1 && -res < INT_MIN) return INT_MIN;
32 } else break;
33 }
34 }
35 return sign * res;
36 }
37};
38
39int main() {
40 Solution sol;
41 std::cout << sol.myAtoi(" -42") << std::endl; // -42
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) — FSM processes characters in O(1) state lookup per char.
  • Space complexity: O(1)

3. Direct 32-bit Integer Lookahead Clamping (Optimal)

Intuition

1. Skip whitespace. 2. Capture sign. 3. For each digit d = s[i] - '0', check if total > INT_MAX / 10 || (total == INT_MAX / 10 && d > 7). If true, return sign == 1 ? INT_MAX : INT_MIN. Otherwise, total = total * 10 + d. Return sign * total.

When to apply: The standard gold standard solution for 32-bit compliance.

Algorithm

  1. Initialize i = 0, sign = 1, total = 0, n = s.length.
  2. While i < n && s[i] == ' ': i++.
  3. If i < n && (s[i] == '+' || s[i] == '-'): sign = (s[i] == '-') ? -1 : 1; i++.
  4. While i < n && s[i] >= '0' && s[i] <= '9':
  5. digit = s[i] - '0'
  6. If total > 214748364 || (total == 214748364 && digit > 7):
  7. Return sign == 1 ? 2147483647 : -2147483648.
  8. total = total * 10 + digit.
  9. i++.
  10. Return sign * total.

Deterministic Finite Automaton Clamping Parser

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [ , , , -, 4, 2, , w, o, r, d, s]
Current operationSTEP 1 OF 6
Observation: Read characters at indices 0, 1, 2: all whitespace ' '
Visual state
Values and pointers at this exact step
array
S
-
4
0
1
2
3
↑ Skip whitespace -> i=3
4
Variables at this step
phase
Skip Whitespace
skippedCount
3
firstNonSpace
-
Why this step matters

Observation: Read characters at indices 0, 1, 2: all whitespace ' '.

Decision: Advance pointer past spaces to index 3 ('-').

Invariant: Leading whitespace is safely ignored.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <climits>
4
5class Solution {
6public:
7 int myAtoi(std::string s) {
8 int i = 0, n = s.size();
9 while (i < n && s[i] == ' ') i++;
10 if (i == n) return 0;
11
12 int sign = 1;
13 if (s[i] == '+' || s[i] == '-') {
14 sign = (s[i] == '-') ? -1 : 1;
15 i++;
16 }
17
18 int total = 0;
19 while (i < n && s[i] >= '0' && s[i] <= '9') {
20 int digit = s[i] - '0';
21
22 // Check overflow before multiplying
23 if (total > INT_MAX / 10 || (total == INT_MAX / 10 && digit > INT_MAX % 10)) {
24 return sign == 1 ? INT_MAX : INT_MIN;
25 }
26
27 total = total * 10 + digit;
28 i++;
29 }
30
31 return sign * total;
32 }
33};
34
35int main() {
36 Solution sol;
37 std::cout << sol.myAtoi("42") << std::endl; // 42
38 std::cout << sol.myAtoi(" -042") << std::endl; // -42
39 std::cout << sol.myAtoi("-91283472332") << std::endl; // -2147483648
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) — Single forward pass with pure primitive integer operations.
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.64-bit Long Accumulation with ClampingO(N)O(1)Simple arithmetic using 64-bit integer type.Not viable in strictly 32-bit embedded platforms without 64-bit registers.
2.Finite State Machine (FSM / DFA)O(N)O(1)Formal parser design, scalable to complex grammar rules.State transition table boilerplate.
3.32-bit Direct Arithmetic with Lookahead Overflow Check (Optimal)OptimalO(N)O(1) extra spacePure 32-bit arithmetic, zero 64-bit dependency, fastest execution.Requires exact boundary comparison ans > INT_MAX / 10 || (ans == INT_MAX / 10 && digit > 7).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Letting 32-bit signed integer overflow into undefined behavior before checking limits.

Pitfall 2:

Forgetting to check the trailing digit digit > 7 when total == INT_MAX / 10.

Crucial Edge Cases to Validate:

  • Empty or whitespace-only string (s = ' '): i reaches end of string, returns 0.
  • Double sign (s = +-12): First + sets sign; - triggers non-digit termination, returns 0.
  • Massive integer exceeding 32-bit boundaries (s = -999999999999): Overflow check triggers immediately and clamps to INT_MIN (-2147483648).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the 32-bit boundary threshold INT_MAX / 10 and remainder 7 clearly.
  2. Walk the interviewer through the exact order: spaces -> sign -> digits -> clamping.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the overflow threshold comparison total > INT_MAX / 10 || (total == INT_MAX / 10 && digit > 7) used?

Back to DSA Sheet