How do you solve Basic Calculator on LeetCode?

Basic Calculator (LeetCode #224) 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: Using a stack allows us to handle nested expressions and operator precedence effectively.

What is the time complexity of Basic Calculator?

The optimal solution for Basic Calculator runs in O(n) time and uses O(n) space. The complexity is O(n) because we traverse the string once, and the stack operations (push/pop) are O(1).

What is the brute force solution for Basic Calculator?

The brute force approach for Basic Calculator is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves parsing the string character by character and evaluating the expression directly. This method is straightforward but inefficient, as it may require multiple passes over the string to handle parentheses and operator precedence. The optimal Optimal Solution approach improves this to O(n).

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

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

What are the interview tips for Basic Calculator?

Explain your thought process clearly while coding, especially how you handle operators and parentheses. Be mindful of edge cases, such as expressions with multiple nested parentheses. Practice writing clean and efficient code, as readability is important in interviews.

What are common mistakes when solving Basic Calculator?

Forgetting to reset the current number after processing an operator. Not handling parentheses correctly, leading to incorrect results.

#224

Basic Calculator

Hard

MathStringStackRecursionStackRecursion

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 parentheses and operator precedence efficiently. By processing the string in one pass and utilizing a stack to manage results and signs, we achieve a linear time complexity.

⚙️

Algorithm

5 steps

1Step 1: Initialize a stack to keep track of results and signs.
2Step 2: Traverse the string character by character, building numbers and handling operators.
3Step 3: When encountering '(', push the current result and sign onto the stack.
4Step 4: When encountering ')', pop from the stack to combine the results.
5Step 5: Return the final computed result after processing all characters.

solution.py32 lines

1# Full working Python code
2class BasicCalculator:
3    def calculate(self, s: str) -> int:
4        stack = []
5        current_number = 0
6        result = 0
7        sign = 1
8
9        for char in s:
10            if char.isdigit():
11                current_number = current_number * 10 + int(char)
12            elif char == '+':
13                result += sign * current_number
14                current_number = 0
15                sign = 1
16            elif char == '-':
17                result += sign * current_number
18                current_number = 0
19                sign = -1
20            elif char == '(':  
21                stack.append(result)
22                stack.append(sign)
23                result = 0
24                sign = 1
25            elif char == ')':
26                result += sign * current_number
27                result *= stack.pop()  # sign before the '('
28                result += stack.pop()  # result before the '('
29                current_number = 0
30
31        return result + sign * current_number
32

ℹ

Complexity note: The complexity is O(n) because we traverse the string once, and the stack operations (push/pop) are O(1).

1Using a stack allows us to handle nested expressions and operator precedence effectively.
2Managing signs and results separately helps in simplifying the evaluation process.

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