Scale Engineer

Minimize Result by Adding Parentheses to Expression

Med
#2033Time: O(L * R * N), where `L` is the length of the first number, `R` is the length of the second number, and `N` is the total length of the expression. The nested loops run `L * R` times. Inside the loop, `substring` operations, `parseLong`, and string concatenation take `O(N)` time in total. Given `N <= 10`, this is very fast.Space: O(N) to store the resulting string, where N is the length of the expression.2 companies
Patterns
Enumeration
Data structures
String
Companies
SnapPinterest

Prompt

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:

expression

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:

expression

 

Constraints:

  • 3 <= expression.length <= 10
  • expression consists of digits from '1' to '9' and '+'.
  • expression starts and ends with digits.
  • expression contains exactly one '+'.
  • 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically explores every possible valid placement for the parentheses. For each placement, it calculates the resulting expression's value and keeps track of the placement that yields the minimum value found so far.

Algorithm

  • Find the index of the + sign, let's call it plusIndex.
  • Initialize minVal to infinity and resultExpression to an empty string.
  • Iterate with a loop for the left parenthesis position i from 0 to plusIndex - 1.
  • Inside this loop, iterate with another loop for the right parenthesis position j from plusIndex + 1 to expression.length() - 1.
  • In the inner loop:
    • Split the expression into four parts based on i and j.
    • Parse these parts into numbers, treating empty parts as multipliers of 1.
    • Calculate the value of the expression part1 * (part2 + part3) * part4.
    • If the calculated value is smaller than minVal:
      • Update minVal with the new smaller value.
      • Construct the parenthesized string and update resultExpression.
  • Return resultExpression.

Walkthrough

The core idea is to iterate through all possible split points for the two numbers around the + sign. Let the expression be num1+num2. The left parenthesis ( can be inserted at any position within num1, and the right parenthesis ) can be inserted at any position within num2. This partitions the expression into four parts: A(B+C)D.

  • A: The part of num1 before the (. Can be empty.
  • B: The part of num1 after the (.
  • C: The part of num2 before the ).
  • D: The part of num2 after the ). Can be empty.

The value of the expression is val(A) * (val(B) + val(C)) * val(D). If A or D is empty, its value is considered 1.

The algorithm proceeds as follows:

  1. Find the index of the + operator.
  2. Initialize minVal to a very large number and result to an empty string.
  3. Use a nested loop:
    • The outer loop iterates through all possible positions i to place the (. This position i splits num1.
    • The inner loop iterates through all possible positions j to place the ). This position j splits num2.
  4. Inside the loops, for each pair of (i, j): a. Extract the four substrings corresponding to A, B, C, and D. b. Parse them into integers. Handle empty strings for A and D by using a value of 1. c. Calculate the total value: valA * (valB + valC) * valD. d. If this value is less than minVal, update minVal and reconstruct the entire expression string with parentheses at the current positions i and j. Store this new string in result.
  5. After checking all possibilities, result will hold the expression that evaluates to the smallest value.
class Solution {    public String minimizeResult(String expression) {        int plusIndex = expression.indexOf('+');        long minVal = Long.MAX_VALUE;        String result = "";         // i is the split point for the left number (num1)        // It's the index where '(' is inserted.        for (int i = 0; i < plusIndex; i++) {            // j is the split point for the right number (num2)            // It's the index of the last digit inside the parenthesis.            for (int j = plusIndex + 1; j < expression.length(); j++) {                // Part 1: Left multiplier                String p1Str = expression.substring(0, i);                long p1 = p1Str.isEmpty() ? 1 : Long.parseLong(p1Str);                 // Part 2: First number in sum                String p2Str = expression.substring(i, plusIndex);                long p2 = Long.parseLong(p2Str);                 // Part 3: Second number in sum                String p3Str = expression.substring(plusIndex + 1, j + 1);                long p3 = Long.parseLong(p3Str);                 // Part 4: Right multiplier                String p4Str = expression.substring(j + 1);                long p4 = p4Str.isEmpty() ? 1 : Long.parseLong(p4Str);                 long currentVal = p1 * (p2 + p3) * p4;                 if (currentVal < minVal) {                    minVal = currentVal;                    result = p1Str + "(" + p2Str + "+" + p3Str + ")" + p4Str;                }            }        }        return result;    }}

Complexity

Time

O(L * R * N), where `L` is the length of the first number, `R` is the length of the second number, and `N` is the total length of the expression. The nested loops run `L * R` times. Inside the loop, `substring` operations, `parseLong`, and string concatenation take `O(N)` time in total. Given `N <= 10`, this is very fast.

Space

O(N) to store the resulting string, where N is the length of the expression.

Trade-offs

Pros

  • Guaranteed to find the optimal solution because it checks every possibility.

  • Simple and straightforward to implement.

Cons

  • Inefficient due to repeated string construction inside the loops. For each new minimum found, a new result string is created, which involves memory allocation and copying.

Solutions

class Solution {public  String minimizeResult(String expression) {    int idx = expression.indexOf('+');    String l = expression.substring(0, idx);    String r = expression.substring(idx + 1);    int m = l.length(), n = r.length();    int mi = Integer.MAX_VALUE;    String ans = "";    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        int c = Integer.parseInt(l.substring(i)) +                Integer.parseInt(r.substring(0, j + 1));        int a = i == 0 ? 1 : Integer.parseInt(l.substring(0, i));        int b = j == n - 1 ? 1 : Integer.parseInt(r.substring(j + 1));        int t = a * b * c;        if (t < mi) {          mi = t;          ans = String.format("%s(%s+%s)%s", l.substring(0, i), l.substring(i),                              r.substring(0, j + 1), r.substring(j + 1));        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem