You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.
Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.
Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
Input: expression = "247+38" Output: "2(47+38)" Explanation: Theexpressionevaluates to 2 * (47 + 38) = 2 * 85 = 170. Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the'+'. It can be shown that 170 is the smallest possible value.
Example 2:
Input: expression = "12+34" Output: "1(2+3)4" Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
Example 3:
Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
Constraints:
3 <= expression.length <= 10expression consists of digits from '1' to '9' and '+'.expression starts and ends with digits.expression contains exactly one '+'.expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.Problem Overview: You receive a string expression of the form num1+num2. The task is to insert a single pair of parentheses somewhere around the + so the resulting arithmetic value is minimized. Parentheses can extend into the digits on either side, which effectively multiplies surrounding numbers.
Approach 1: Brute Force Strategy From Both Sides (O(n^2) time, O(n) space)
Split the expression around the +. Then enumerate every possible position where the left parenthesis could start in the left number and every position where the right parenthesis could end in the right number. For each pair of positions, construct the expression and evaluate it as leftMultiplier * (insideLeft + insideRight) * rightMultiplier. Missing multipliers default to 1. This works because parentheses effectively isolate a portion of each number around the plus operator. The approach tries all combinations using simple string slicing and enumeration, then tracks the minimum result.
Approach 2: Optimized Computation with Consideration of Edge Cases (O(n^2) time, O(1) space)
The optimized version avoids repeatedly rebuilding strings or performing unnecessary conversions. Instead, iterate over all valid split indices while computing numeric segments directly. For each pair (i, j), treat the expression as four parts: prefix, leftInside, rightInside, and suffix. Convert only the necessary substrings to integers and compute the value using prefix * (leftInside + rightInside) * suffix. Edge cases occur when the prefix or suffix is empty; treat them as multiplier 1. This keeps the evaluation constant-time per configuration while still exploring all valid placements.
Recommended for interviews: Start with the brute force enumeration to show you understand how parentheses affect arithmetic grouping. Then move to the optimized computation that evaluates each candidate using numeric segments instead of constructing full expressions. Interviewers expect the O(n^2) enumeration solution because the search space is small and easy to reason about.
By evaluating each substring from the left of the operator to a point before the `+`, and each substring from right of `+` to the end, compute values assuming parentheses are added at each possible position. This method involves double loops: one iterating over split points for the left number and the other iterating over split points for the right number. Since the expression is small in size, this approach won't pose efficiency problems. Compute the value by considering the substrings around the `+` if they exist, and update the minimum value when a new lower result is found.
The Python solution uses two nested loops. The outer loop controls the split point in `num1`, and the inner loop controls `num2`. left1 and right1 are derived from num1, and left2 and right2 from num2. If available, empty strings fall back to 1 for calculations. This implementation carefully constructs one possible configuration of parentheses through the string concatenation approach.
Python
JavaScript
C
Since both loops are over a length of the expression, the time complexity is O(n^2). Space complexity is O(n) due to string storage.
This strategy is built upon identifying useful computation patterns but adds optimization by examining secondary computations around very short components ensuring minimum possible outcomes. In particular stretches of the numbers yielding non-obvious values due to edge cases are reviewed; these should be incrementally computed to prevent missed low value outcomes.
The Java solution builds on treating each incorporated possibility with a strategic subroutine. It constructs the result by examining substrings via `substring` methods and calculates each outcome. The systematic examination guarantees minimum result occurs naturally by covering edge subranges of numerical input.
This approach has a time complexity of O(n^2) evaluating all possible splits like before. Space complexity is O(n) because we handle substrings but repeatedly process them rather than storing too many alternatives.
Python
Java
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Strategy From Both Sides | Since both loops are over a length of the expression, the time complexity is |
| Optimized Computation with Consideration of Edge Cases | This approach has a time complexity of |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Strategy From Both Sides | O(n^2) | O(n) | When exploring all parenthesis placements directly using string slicing |
| Optimized Computation with Edge Case Handling | O(n^2) | O(1) | Preferred for interviews when minimizing conversions and computing numeric segments efficiently |
Minimize Result by Adding Parentheses to Expression | Leetcode 2232 | Pointers | Contest 288 🔥🔥 • Coding Decoded • 1,651 views views
Watch 9 more video solutions →Practice Minimize Result by Adding Parentheses to Expression with our built-in code editor and test cases.
Practice on FleetCode