Minimize Result by Adding Parentheses to Expression - Solution & Explanation
Problem Statement
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 <= 10expressionconsists of digits from'1'to'9'and'+'.expressionstarts and ends with digits.expressioncontains exactly one'+'.- The original value of
expression, and the value ofexpressionafter adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Approach Overview
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.
Approach 1: Brute Force Strategy From Both Sides
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.
Code
Python
JavaScript
C
Complexity
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.
Approach 2: Optimized Computation with Consideration of Edge Cases
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.
Complexity
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.
Approach 3: Default Approach
Code
Python
Java
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimize Result by Adding Parentheses to Expression | Leetcode 2232 | Pointers | Contest 288 🔥🔥 • Coding Decoded • 1,687 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimize Result by Adding Parentheses to Expression easy or hard?
Minimize Result by Adding Parentheses to Expression Python/Java solution
How to solve Minimize Result by Adding Parentheses to Expression in O(n)?
What is the best approach for Minimize Result by Adding Parentheses to Expression?
Is Minimize Result by Adding Parentheses to Expression asked at Google/Amazon/Meta?
What data structure is used in Minimize Result by Adding Parentheses to Expression?
What is the time complexity of Minimize Result by Adding Parentheses to Expression?
Ready to solve this problem?
Practice Minimize Result by Adding Parentheses to Expression with our built-in code editor and test cases.
Practice on FleetCode