Skip to main content

Leetcode 8: String to Integer (atoi)


1. Problem Statement (Simple Explanation):


You need to implement:

int myAtoi(string s)

which converts a string s to a 32-bit signed integer, following these rules:

  1. Whitespace:
    Ignore leading spaces " " until you hit the first non-space character.

  2. Sign:
    If the next character is '-' or '+':

    • '-' → number is negative

    • '+' → number is positive
      If neither, assume positive.

  3. Conversion:
    Read digits ('0'–'9') one by one:

    • Skip any leading zeros (i.e., they don’t affect the value).

    • Stop when you encounter a non-digit or end of string.

    • If no digits are read at all → return 0.

  4. Rounding (Clamping):
    If the number goes outside the 32-bit signed range:

                                [-231,231-1]=[-2147483648,2147483647]

                  then:

  • If result < -231 → return -231

  • If result > 231-1 → return 231-1

Return the final integer.


2. Examples:


Example 1:

Input:            s = "42"

Output:         42

Steps:

  • No leading whitespace.

  • No sign → positive.

  • Read "42" → 42.


Example 2:

Input:           s = "-042"

Output:        -42

Steps:

  • Skip " ".

  • See '-' → negative.

  • Read digits "042" → numeric value 42.

  • Apply sign → -42.


Example 3:

Input:        s = "1337c0d3"

Output:     1337

Steps:

  • No leading whitespace.

  • No sign → positive.

  • Read "1337", stop at 'c' (first non-digit).

  • Result 1337.


Example 4:

Input:        s = "0-1"

Output:     0

Steps:

  • No leading whitespace.

  • No sign.

  • Read "0", stop at '-' (non-digit).

  • Result 0.


Example 5:

Input:        s = "words and 987"

Output:     0

Steps:

  • First char 'w' is not space, sign, or digit.

  • No digits read → return 0.


3. Basic Approach – Step-by-Step Parsing (Single Pass):


We parse the string once, left to right.


Algorithm (Step-by-Step):


  1. Start by setting an index i to 0.
     Also store the length of the string n, set the default sign to positive (1), and set result to 0.

  2. Ignore all leading spaces in the string.
     Move i forward until you reach a non-space character or the end of the string.

  3. Check if the current character is a sign symbol:

  • If it is '+', keep the sign positive.

  • If it is '-', change the sign to negative.
     Move the index forward if a sign was found.

  1. Now begin reading characters as long as they are digits:

  • Convert the digit character into its numeric value.

  • Before adding it to result, check if adding this digit would cause an overflow:

    • If result is already larger than INT_MAX / 10, the next multiplication will overflow.

    • If result equals INT_MAX / 10 and the next digit is greater than 7, it will overflow.

  • If an overflow is detected:

    • Return INT_MAX if the sign is positive.

    • Return INT_MIN if the sign is negative.

  • If safe, update the number: multiply result by 10 and add the digit.

  • Move to the next character.

  1. If no digit at all was processed, simply return 0.

  2. Finally, multiply the result by the sign (positive or negative) and return the final number.


Pseudo-code (myAtoi):


Complexity:


Let n be the length of s:

  • Time:    O(n)

One pass over the string.

  • Space:   O(1)

Only a few variables.


4. Java code:



5. C code:



6. C++ code:



7. Python code:


Python’s ints are unbounded, but we simulate 32-bit behavior with clamping.



8. JavaScript:




<<<PREV
NEXT>>>


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more