Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
A complete visual walkthrough of the one-pass character scanning approach — from messy edge cases to a clean state machine.
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
The algorithm for myAtoi(string s) is as follows:
" ").'-' or '+', assuming positivity if neither present.[-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.Return the integer as the final result.
Example 1:
Input: s = "42"
Output: 42
Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
Example 2:
Input: s = " -042"
Output: -42
Explanation:
Step 1: " -042" (leading whitespace is read and ignored)
^
Step 2: " -042" ('-' is read, so the result should be negative)
^
Step 3: " -042" ("042" is read in, leading zeros ignored in the result)
^
Example 3:
Input: s = "1337c0d3"
Output: 1337
Explanation:
Step 1: "1337c0d3" (no characters read because there is no leading whitespace)
^
Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+')
^
Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit)
^
Example 4:
Input: s = "0-1"
Output: 0
Explanation:
Step 1: "0-1" (no characters read because there is no leading whitespace)
^
Step 2: "0-1" (no characters read because there is neither a '-' nor '+')
^
Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit)
^
Example 5:
Input: s = "words and 987"
Output: 0
Explanation:
Reading stops at the first non-digit character 'w'.
Constraints:
0 <= s.length <= 200s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.Many developers reach for regex or try to handle every edge case with nested if-else blocks. Let's see why that gets ugly fast:
// Attempt 1: regex (seems clean... until it isn't) Pattern p = Pattern.compile("^\\s*([+-]?\\d+)"); // But wait — how do you handle overflow? // Long.parseLong("99999999999999999999") throws! // Attempt 2: strip + parse (multiple passes) s = s.trim(); // pass 1: strip whitespace // check sign... // pass 2: inspect sign // extract digits... // pass 3: find digit span // handle overflow somehow... // ??? easy to get wrong
// Attempt 1: regex (seems clean... until it isn't) re := regexp.MustCompile(`^\s*([+-]?\d+)`) // But wait — how do you handle overflow? // strconv.Atoi("99999999999999999999") returns an error // Attempt 2: trim + parse (multiple passes) s = strings.TrimSpace(s) // pass 1: strip whitespace // check sign... // pass 2: inspect sign // extract digits... // pass 3: find digit span // handle overflow somehow... // ??? easy to get wrong
# Attempt 1: regex (seems clean... until it isn't) import re match = re.match(r"^\s*([+-]?\d+)", s) # Python handles big ints natively, # but you still need to clamp to 32-bit range! # Attempt 2: strip + parse (multiple passes) s = s.strip() # pass 1: strip whitespace # check sign... # pass 2: inspect sign # extract digits... # pass 3: find digit span # handle overflow somehow... # ??? easy to get wrong
// Attempt 1: regex (seems clean... until it isn't) // The regex crate works but adds a heavyweight dependency // and still doesn't handle 32-bit overflow automatically // Attempt 2: trim + parse (multiple passes) let s = s.trim_start(); // pass 1: strip whitespace // check sign... // pass 2: inspect sign // extract digits... // pass 3: find digit span // handle overflow somehow... // ??? easy to get wrong
// Attempt 1: regex (seems clean... until it isn't) const match = s.match(/^\s*([+-]?\d+)/); // But wait — how do you handle overflow? // Number.parseInt("99999999999999999999") loses precision! // Attempt 2: trim + parse (multiple passes) s = s.trim(); // pass 1: strip whitespace // check sign... // pass 2: inspect sign // extract digits... // pass 3: find digit span // handle overflow somehow... // ??? easy to get wrong
The problem is not parsing the happy path. It's handling all the edge cases simultaneously: leading whitespace, optional sign, leading zeros, overflow mid-parse, and non-digit characters appearing anywhere.
The real challenge: You must detect overflow before it happens, during digit accumulation. You can't just parse and then clamp afterward because the intermediate value might already overflow your integer type.
Instead of fighting edge cases, think of the problem as a simple state machine with four states. Process the string character by character in a single left-to-right pass:
Each state either consumes characters and advances to the next, or transitions directly to DONE. There is no backtracking. The pointer moves forward exactly once per character.
s[i] == ' ', advance i++. Any other character transitions to the next state.s[i] is + or -, record the sign and advance. This state consumes at most one character.s[i] is a digit, accumulate: result = result * 10 + digit. Check for overflow before each multiplication.The overflow trick: Before computing result * 10 + digit, check if result > (MAX_VALUE - digit) / 10. If true, the next multiplication would overflow, so clamp immediately. This avoids ever storing a value that exceeds 32-bit bounds.
Let's trace through the input " -42abc" character by character. Watch the pointer advance through each phase.
' '. Skip them. Pointer lands on i = 3.'-'. Set sign = -1. Advance to i = 4.0 > (2147483647 - 4) / 10? No. result = 0 * 10 + 4 = 4. Advance to i = 5.4 > (2147483647 - 2) / 10? No. result = 4 * 10 + 2 = 42. Advance to i = 6.'a' is not a digit. Exit the loop.This problem is essentially an edge-case gauntlet. Here are all the tricky inputs and what the algorithm returns for each:
No special cases needed. The beauty of the one-pass approach is that every edge case above is handled naturally by the same three-phase loop. There are no separate if branches for empty strings, sign-only inputs, or leading zeros.
class Solution { public int myAtoi(String s) { int i = 0, n = s.length(); // -------- Phase 1: Skip leading whitespace -------- while (i < n && s.charAt(i) == ' ') i++; if (i == n) return 0; // entire string was spaces // -------- Phase 2: Read optional sign -------- int sign = 1; if (s.charAt(i) == '-' || s.charAt(i) == '+') { sign = s.charAt(i) == '-' ? -1 : 1; i++; // consume the sign character } // -------- Phase 3: Read digits with overflow guard -------- int result = 0; while (i < n && Character.isDigit(s.charAt(i))) { int digit = s.charAt(i) - '0'; // Will result * 10 + digit overflow int? // Rearranged: result > (MAX_VALUE - digit) / 10 if (result > (Integer.MAX_VALUE - digit) / 10) { return sign == 1 ? Integer.MAX_VALUE // 2147483647 : Integer.MIN_VALUE; // -2147483648 } result = result * 10 + digit; // safe to accumulate i++; } return result * sign; } }
func myAtoi(s string) int { i, n := 0, len(s) const intMax, intMin = 1<<31 - 1, -1 << 31 // -------- Phase 1: Skip leading whitespace -------- for i < n && s[i] == ' ' { i++ } if i == n { return 0 // entire string was spaces } // -------- Phase 2: Read optional sign -------- sign := 1 if s[i] == '-' || s[i] == '+' { if s[i] == '-' { sign = -1 } i++ // consume the sign character } // -------- Phase 3: Read digits with overflow guard -------- result := 0 for i < n && s[i] >= '0' && s[i] <= '9' { digit := int(s[i] - '0') // Will result * 10 + digit overflow 32-bit int? if result > (intMax-digit)/10 { if sign == 1 { return intMax } return intMin } result = result*10 + digit // safe to accumulate i++ } return result * sign }
class Solution: def my_atoi(self, s: str) -> int: i, n = 0, len(s) INT_MAX, INT_MIN = 2147483647, -2147483648 # -------- Phase 1: Skip leading whitespace -------- while i < n and s[i] == ' ': i += 1 if i == n: return 0 # entire string was spaces # -------- Phase 2: Read optional sign -------- sign = 1 if s[i] == '-' or s[i] == '+': sign = -1 if s[i] == '-' else 1 i += 1 # consume the sign character # -------- Phase 3: Read digits with overflow guard -------- result = 0 while i < n and s[i].isdigit(): digit = ord(s[i]) - ord('0') # Will result * 10 + digit overflow 32-bit int? if result > (INT_MAX - digit) // 10: return INT_MAX if sign == 1 else INT_MIN result = result * 10 + digit # safe to accumulate i += 1 return result * sign
impl Solution { pub fn my_atoi(s: String) -> i32 { let bytes = s.as_bytes(); let n = bytes.len(); let mut i = 0; // -------- Phase 1: Skip leading whitespace -------- while i < n && bytes[i] == b' ' { i += 1; } if i == n { return 0; // entire string was spaces } // -------- Phase 2: Read optional sign -------- let mut sign: i32 = 1; if bytes[i] == b'-' || bytes[i] == b'+' { if bytes[i] == b'-' { sign = -1; } i += 1; // consume the sign character } // -------- Phase 3: Read digits with overflow guard -------- let mut result: i32 = 0; while i < n && bytes[i].is_ascii_digit() { let digit = (bytes[i] - b'0') as i32; // Will result * 10 + digit overflow i32? if result > (i32::MAX - digit) / 10 { return if sign == 1 { i32::MAX } else { i32::MIN }; } result = result * 10 + digit; // safe to accumulate i += 1; } result * sign } }
function myAtoi(s: string): number { let i = 0; const n = s.length; const INT_MAX = 2147483647, INT_MIN = -2147483648; // -------- Phase 1: Skip leading whitespace -------- while (i < n && s[i] === ' ') i++; if (i === n) return 0; // entire string was spaces // -------- Phase 2: Read optional sign -------- let sign = 1; if (s[i] === '-' || s[i] === '+') { sign = s[i] === '-' ? -1 : 1; i++; // consume the sign character } // -------- Phase 3: Read digits with overflow guard -------- let result = 0; while (i < n && s[i] >= '0' && s[i] <= '9') { const digit = s.charCodeAt(i) - 48; // '0' is 48 // Will result * 10 + digit overflow 32-bit int? if (result > Math.floor((INT_MAX - digit) / 10)) { return sign === 1 ? INT_MAX : INT_MIN; } result = result * 10 + digit; // safe to accumulate i++; } return result * sign; }
Why the overflow check works: We want to know if result * 10 + digit > 2147483647. Rearranging gives result > (2147483647 - digit) / 10. Since all values are positive integers and we're using integer division, this comparison is safe and never overflows itself.
Enter any string and step through the atoi algorithm character by character. Watch the state machine in action.
We scan each character at most once in a single left-to-right pass. The pointer i never moves backward, and the overflow check (result > (MAX_VALUE - digit) / 10) is O(1) per digit. We use only a fixed number of variables (i, sign, result, digit) regardless of input size.
A regex engine compiles the pattern and scans the string in O(n), but internally creates match objects and substring copies that allocate O(n) memory. Multi-pass approaches (trim, then find sign, then extract digits) also traverse the string multiple times, though still linear overall.
A single left-to-right scan with a three-phase state machine (skip whitespace, read sign, accumulate digits) touches each character exactly once for O(n) time. Only a fixed number of integer variables (i, sign, result, digit) are used regardless of input length, giving O(1) space.
The complexity isn't the hard part here. Both approaches are O(n) in time. The real challenge is detecting overflow before it happens, using the rearranged check result > (MAX_VALUE - digit) / 10. That single line is the difference between a correct solution and a subtle bug.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.