Jobs

Interviews

Discussions

Basic Calculator II

Medium

Basic Calculator II

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the non-negative integers in the input string, and should I expect the result to fit within the standard integer range?
Can the input string be empty or null, and if so, what should I return?
Are parentheses allowed in the expression, or only the operators +, -, *, and /?
How should I handle division by zero? Should I throw an error, return a specific value (e.g., 0 or infinity), or is it guaranteed that there will be no division by zero?
Besides spaces, are there any other invalid characters that might appear in the input string? If so, how should I handle them?

Brute Force Solution

Approach

The most straightforward way to solve this is to evaluate the expression piece by piece. We read the entire input and perform calculations in the order we encounter the operators.

Here's how the algorithm would work step-by-step:

Read the input expression from left to right.
Keep track of the current number and the previous operator.
Whenever you encounter a number, update the current number accordingly.
When you encounter an operator, perform the previous operation with the current number, based on the previous operator. Note that we need to consider operator precedence.
If the current operator is multiplication or division, immediately perform that operation with the number that follows it. Then continue scanning.
If the current operator is addition or subtraction, save the current number, and continue to the next operand.
Once you've read the entire expression, apply all pending addition and subtraction operations to arrive at the final result.

Code Implementation

def calculate(input_string):    current_number = 0
    previous_operator = '+'
    stack = []
    string_length = len(input_string)

    for index in range(string_length):        character = input_string[index]

        if character.isdigit():            current_number = (current_number * 10) + int(character)

        if character in '+-*/' or index == string_length - 1:
            # Apply previous operator and update the stack for +/-
            if previous_operator == '+':
                stack.append(current_number)
            elif previous_operator == '-':
                stack.append(-current_number)
            elif previous_operator == '*':
                stack.append(stack.pop() * current_number)
            else:
                stack.append(int(stack.pop() / current_number))

            previous_operator = character
            current_number = 0

    # Sum up remaining values in stack after mult/div are processed.
    result = sum(stack)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once to process numbers and operators. While multiplication and division are performed immediately, they don't introduce nested loops or recursion. The pending addition and subtraction operations at the end are also performed in a single pass based on the processed numbers. Therefore, the time complexity is directly proportional to the length of the input string n, resulting in O(n).

Space Complexity

O(1) – The algorithm described stores the 'current number' and the 'previous operator'. It also potentially needs to store the result of intermediate calculations from multiplication and division before applying addition and subtraction. However, it doesn't mention using any additional data structures like lists or hash maps that scale with the input size, N (length of the expression string). Therefore, the auxiliary space used remains constant, independent of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

The efficient solution handles math problems in a specific order, focusing on the most important operations first. It processes multiplication and division before addition and subtraction to get the correct result without needing parentheses. This prevents the need to evaluate the entire equation at once, thus saving time and space.

Here's how the algorithm would work step-by-step:

First, go through the entire math problem and do all the multiplication and division. Instead of actually calculating the final results right away, just keep track of the intermediate values and their signs (positive or negative).
Imagine creating a new simplified math problem with only additions and subtractions, where each number has a sign (+ or -) calculated in the first step.
Next, go through this simplified problem and add or subtract the numbers based on their signs to get the final answer.

Code Implementation

def calculate(expression):
    current_number = 0
    stack = []
    last_operation = '+'

    for i, character in enumerate(expression):
        if character.isdigit():
            current_number = (current_number * 10) + int(character)

        if character in '+-*/' or i == len(expression) - 1:
            # Perform multiplication and division before addition and subtraction.
            if last_operation == '+':
                stack.append(current_number)
            elif last_operation == '-':
                stack.append(-current_number)
            elif last_operation == '*':
                stack.append(stack.pop() * current_number)
            else:
                stack.append(int(stack.pop() / current_number))

            last_operation = character
            current_number = 0

    # Sum up the stack to get the final result.
    result = 0
    while stack:
        result += stack.pop()
    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string twice. The first pass handles multiplication and division, while the second pass performs addition and subtraction on the intermediate results. Both passes iterate through the string once, where 'n' represents the length of the input string. Since we perform two independent linear passes through the string, the time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a data structure (implicitly described as 'keeping track of intermediate values and their signs') to store the results of multiplication and division. In the worst case, where there are no additions or subtractions in the input string of length N, the algorithm needs to store up to N/2 numbers (after multiplication and division operations), each with an associated sign. Therefore, the auxiliary space used scales linearly with the input size, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty or null input string	Return 0 immediately as there's nothing to calculate.
String containing only whitespace	Return 0 as the expression is essentially empty.
String with a single number	Return the number itself (after trimming whitespace).
String starting or ending with an operator	Prepend '0+' to the string to handle the start and treat the end as incomplete, properly handling these operators.
Consecutive operators or multiple spaces between numbers and operators	Filter out unnecessary spaces and handle consecutive operators based on precedence.
Integer overflow during calculation	Use long type to prevent integer overflow during intermediate calculations and cast back to int for the final result.
Division by zero	The problem description states integer division should truncate toward zero, implying division by zero won't occur but if it does, the environment will dictate the behavior (usually an exception or undefined result).
Very long input string (performance)	Iterative solution avoids stack overflow issues of recursion, and with O(n) complexity based on string length provides linear performance.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the non-negative integers in the input string, and should I expect the result to fit within the standard integer range?
Can the input string be empty or null, and if so, what should I return?
Are parentheses allowed in the expression, or only the operators +, -, *, and /?
How should I handle division by zero? Should I throw an error, return a specific value (e.g., 0 or infinity), or is it guaranteed that there will be no division by zero?
Besides spaces, are there any other invalid characters that might appear in the input string? If so, how should I handle them?

Brute Force Solution

Approach

The most straightforward way to solve this is to evaluate the expression piece by piece. We read the entire input and perform calculations in the order we encounter the operators.

Here's how the algorithm would work step-by-step:

Read the input expression from left to right.
Keep track of the current number and the previous operator.
Whenever you encounter a number, update the current number accordingly.
When you encounter an operator, perform the previous operation with the current number, based on the previous operator. Note that we need to consider operator precedence.
If the current operator is multiplication or division, immediately perform that operation with the number that follows it. Then continue scanning.
If the current operator is addition or subtraction, save the current number, and continue to the next operand.
Once you've read the entire expression, apply all pending addition and subtraction operations to arrive at the final result.

Code Implementation

def calculate(input_string):    current_number = 0
    previous_operator = '+'
    stack = []
    string_length = len(input_string)

    for index in range(string_length):        character = input_string[index]

        if character.isdigit():            current_number = (current_number * 10) + int(character)

        if character in '+-*/' or index == string_length - 1:
            # Apply previous operator and update the stack for +/-
            if previous_operator == '+':
                stack.append(current_number)
            elif previous_operator == '-':
                stack.append(-current_number)
            elif previous_operator == '*':
                stack.append(stack.pop() * current_number)
            else:
                stack.append(int(stack.pop() / current_number))

            previous_operator = character
            current_number = 0

    # Sum up remaining values in stack after mult/div are processed.
    result = sum(stack)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, go through the entire math problem and do all the multiplication and division. Instead of actually calculating the final results right away, just keep track of the intermediate values and their signs (positive or negative).
Imagine creating a new simplified math problem with only additions and subtractions, where each number has a sign (+ or -) calculated in the first step.
Next, go through this simplified problem and add or subtract the numbers based on their signs to get the final answer.

Code Implementation

def calculate(expression):
    current_number = 0
    stack = []
    last_operation = '+'

    for i, character in enumerate(expression):
        if character.isdigit():
            current_number = (current_number * 10) + int(character)

        if character in '+-*/' or i == len(expression) - 1:
            # Perform multiplication and division before addition and subtraction.
            if last_operation == '+':
                stack.append(current_number)
            elif last_operation == '-':
                stack.append(-current_number)
            elif last_operation == '*':
                stack.append(stack.pop() * current_number)
            else:
                stack.append(int(stack.pop() / current_number))

            last_operation = character
            current_number = 0

    # Sum up the stack to get the final result.
    result = 0
    while stack:
        result += stack.pop()
    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input string	Return 0 immediately as there's nothing to calculate.
String containing only whitespace	Return 0 as the expression is essentially empty.
String with a single number	Return the number itself (after trimming whitespace).
String starting or ending with an operator	Prepend '0+' to the string to handle the start and treat the end as incomplete, properly handling these operators.
Consecutive operators or multiple spaces between numbers and operators	Filter out unnecessary spaces and handle consecutive operators based on precedence.
Integer overflow during calculation	Use long type to prevent integer overflow during intermediate calculations and cast back to int for the final result.
Division by zero	The problem description states integer division should truncate toward zero, implying division by zero won't occur but if it does, the environment will dictate the behavior (usually an exception or undefined result).
Very long input string (performance)	Iterative solution avoids stack overflow issues of recursion, and with O(n) complexity based on string length provides linear performance.