8. String to Integer (atoi)

At a Glance

• Topic: math-geometry
• Pattern: Parsing (state / deterministic scan)
• Difficulty: Medium
• Companies: Amazon, Microsoft, Facebook, Bloomberg, Uber
• Frequency: High
• LeetCode: 8

Problem (one-liner)

Implement C-style atoi: skip leading whitespace, optional +/-, then read digits until non-digit; build value with 32-bit signed clamp to [INT32_MIN, INT32_MAX].

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Implement atoi"
• Whitespace rules, sign, overflow clamp (not wrap)
• Stop at first invalid character after digits start

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — regex capture — works but easy to miss edge cases.
• Optimal — single linear scan with phase flags — O(length) time / O(1) space.

Optimal Solution

Go

package main

import "math"

func myAtoi(input string) int {
	index := 0
	for index < len(input) && input[index] == ' ' {
		index++
	}
	sign := 1
	if index < len(input) && (input[index] == '+' || input[index] == '-') {
		if input[index] == '-' {
			sign = -1
		}
		index++
	}
	var accumulate int64 = 0
	for index < len(input) && input[index] >= '0' && input[index] <= '9' {
		digit := int64(input[index] - '0')
		accumulate = accumulate*10 + digit
		if sign == 1 && accumulate > math.MaxInt32 {
			return math.MaxInt32
		}
		negLimit := int64(-math.MinInt32)
		if sign == -1 && accumulate > negLimit {
			return math.MinInt32
		}
		index++
	}
	return sign * int(accumulate)
}

JavaScript

const INT32_MAX = 2147483647;
const INT32_MIN = -2147483648;

function myAtoi(input) {
	let index = 0;
	while (index < input.length && input[index] === ' ') {
		index++;
	}
	let sign = 1;
	if (index < input.length && (input[index] === '+' || input[index] === '-')) {
		if (input[index] === '-') {
			sign = -1;
		}
		index++;
	}
	let result = 0;
	while (index < input.length && input[index] >= '0' && input[index] <= '9') {
		const digit = input.charCodeAt(index) - '0'.charCodeAt(0);
		const maxDigit = sign === 1 ? 7 : 8;
		if (
			result > Math.trunc(INT32_MAX / 10) ||
			(result === Math.trunc(INT32_MAX / 10) && digit > maxDigit)
		) {
			return sign === 1 ? INT32_MAX : INT32_MIN;
		}
		result = result * 10 + digit;
		index++;
	}
	return sign * result;
}

Walkthrough

Input: " -4193with words"

Invariant: result stays within clampable build path; overflow triggers early exit to boundary.

Edge Cases

• Empty or whitespace-only → 0
• "+-12" → 0 (no digits after sign chaos per rules)
• Overflow during accumulation

Pitfalls

• Clamping before multiply overflow on negative side — symmetric checks
• Reading past string bounds

Similar Problems

• 007. Reverse Integer — overflow discipline.
• 066. Plus One — digit-wise numeric semantics.

Variants

• Parse float with exponent rules.
• Locale-aware thousands separators (not LeetCode atoi).

Mind-Map Tags

#parsing #atoi #overflow-clamp #string-scan