How do you solve Basic Calculator II on LeetCode?

Basic Calculator II (LeetCode #227) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding operator precedence is crucial; multiplication and division should be handled immediately, while addition and subtraction can be deferred.

What is the brute force solution for Basic Calculator II?

The brute force approach for Basic Calculator II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach evaluates the expression by parsing it character by character, handling operations as they appear. This method is straightforward but inefficient, especially for longer expressions, as it may require multiple passes to compute the result. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Basic Calculator II?

Basic Calculator II uses the following concepts: Math, String, Stack. The recommended patterns to study are: Stack, Two Pointers.

What are the interview tips for Basic Calculator II?

Always clarify the problem constraints and edge cases before diving into coding. Talk through your thought process while coding; it helps interviewers understand your approach. Test your solution with multiple examples, especially edge cases, to ensure correctness.

What are common mistakes when solving Basic Calculator II?

Forgetting to handle spaces in the input string can lead to incorrect parsing. Not considering the order of operations can result in wrong answers.

#227

Basic Calculator II

Medium

MathStringStackStackTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a stack to handle operations efficiently and processes the expression in a single pass. By leveraging the stack, we can handle multiplication and division immediately, while addition and subtraction are deferred until the end.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty stack, a current number variable, and an operator.
2Step 2: Iterate through the string, building numbers and handling operators as they appear.
3Step 3: For '+', push the current number onto the stack; for '-', push the negative current number.
4Step 4: For '*' and '/', immediately compute the result with the top of the stack and the current number.
5Step 5: At the end of the iteration, sum all values in the stack for the final result.

solution.py22 lines

1# Full working Python code
2class Solution:
3    def calculate(self, s: str) -> int:
4        stack = []
5        current_number = 0
6        operation = '+'
7        s += '+'  # Append a '+' to handle the last number
8        for char in s:
9            if char.isdigit():
10                current_number = current_number * 10 + int(char)
11            elif char in '+-*/':
12                if operation == '+':
13                    stack.append(current_number)
14                elif operation == '-':
15                    stack.append(-current_number)
16                elif operation == '*':
17                    stack[-1] *= current_number
18                elif operation == '/':
19                    stack[-1] = int(stack[-1] / current_number)
20                operation = char
21                current_number = 0
22        return sum(stack)

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once, and the space complexity is O(n) due to the stack storing intermediate results.

1Understanding operator precedence is crucial; multiplication and division should be handled immediately, while addition and subtraction can be deferred.
2Using a stack allows us to manage intermediate results efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.