**Solution in Python**

**Cases to handle**

- leading white spaces in the input string have to be removed
- First non-whitespace character could be an optional '+' or '-' symbol indicating sign of the number followed by as many numerical digits as possible which is interpreted as a numeric value.
- Additional characters after those that form the integral number, should be ignored and should have no effect on the behavior of this function
- If no valid conversion could be performed, a zero value is returned.
- If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

**Approach #1 (Regex) [Accepted]**

The regex approach uses the re module from the python standard library. We write a regular expression to match all strings that have leading white spaces followed by an optional '+' or '-' followed by digits.

We use a try-catch block to handle the condition that If no valid conversion could be performed, a zero value is returned.

Once we get the desired string, it can be converted to an integer and returned after checking for overflow conditions.

```
def myAtoi(self, str):
try:
a = int(re.match(r'\s*[\+|-]?\d*',str).group())
if a>2147483647:
return 2147483647
if a<-2147483648:
return -2147483648
return a
except:
return 0
```

**Complexity Analysis**

- Time complexity :
*O(2n)*=*O(n)*. In the worst case each character will be visited twice. First for regex pattern matching and then for casting the string obtained by the regex to int. - Space complexity :
*O(n)*. In the worst case (assuming all characters in the input string are numbers , we will be storing n element string in memory which we obtain as the output of the regex.

**Approach #2 (character comparison) [Accepted]**

The previous approach suffered from the draw back that we were visiting each character twice.

The solution can be improved upon by removing the dependency on the re module.

Mathematically - The number can be built from each digit obtained in sequence using the following formula -

```
num = num *10 + digit
```

where num is initialized to zero and digit is each numeric character obtained from the string as we read the string from left to right

```
An Integer `1234` can be formed as shown below.
Step1: 1
Step2: 1*10 + 2 = 10 + 2 = 12
Step3: 12*10 + 3 = 120 + 3 = 123
Step4: 123*10 + 4 = 1230 + 4 = 1234
```

```
def myAtoi(self, str):
res = 0
str = str.lstrip()
try:
if str[0] == '+':
sign = 1
elif str[0] == '-':
sign = -1
elif 48<=ord(str[0])<=57:
sign = 1
res = res*10 + (ord(str[0])-48)
else:
return 0
for ch in str[1::]:
if 48<=ord(ch)<=57:
res=res*10+(ord(ch)-48)
else:
break
if (res*sign)>2147483647:
return 2147483647
elif (res*sign)<-2147483648:
return -2147483648
else:
return res*sign
except:
return 0
```

**Complexity Analysis**

- Time complexity :
*O(n)*. In the worst case each character will be visited once. - Space complexity :
*O(1)*This is a constant time algorithm as the memory usage is independent of the size of the input string.

**Approach #3 (character comparison - without built-in functions) [Accepted]**

The above solution can be rewritten to remove the dependency on the function str.lstrip().

We use an additional variable that helps us break out of the loop if there is a space character after numeric digits in the string but if the same space is present as a leading space in the input string we pass over to next character until we encounter a non-white space character.

The time and space complexity remains the same as Approach 2.

```
def myAtoi(self, str):
res = 0
temp = 0
temp1 = 0
sign = 1
if str == "":
return 0
try:
for ch in str:
if temp>=2:
return res
elif ch==" ":
if (temp>=1) or (temp1>0):
break
else:
pass
elif ch == "+":
temp = temp+1
sign = 1
elif ch == "-":
sign = -1
temp = temp+1
elif 48<=ord(ch)<=57:
temp1 = temp1+1
res = res*10 + (ord(ch)-48)
else:
break
sum = res*sign
if sum>2147483647:
return 2147483647
elif sum<-2147483648:
return -2147483648
else:
return sum
except:
return 0
```

**Complexity Analysis**

- Time complexity :
*O(n)*. In the worst case each character will be visited once. - Space complexity :
*O(1)*This is a constant time algorithm as the memory usage is independent of the size of the input string.