Minimum Cost to Change the Final Value of Expression: Stack DP on Boolean Expressions

Boolean expressions look simple on the surface. You have 0, 1, &, |, and parentheses. Evaluating them is something you can do in your head. But LeetCode 1896: Minimum Cost to Change the Final Value of Expression asks a deeper question: what is the minimum number of changes (flip a value or swap an operator) needed to make the expression evaluate to the opposite result?

This problem is rated Hard, and for good reason. It combines expression parsing with dynamic programming in a way that forces you to track two things at once: the value of each subexpression and the minimum cost to flip that value. If you have solved Basic Calculator or Evaluate Reverse Polish Notation, you already have the stack parsing piece. The DP layer on top is what makes this one special.

The problem

You are given a valid boolean expression as a string. The expression contains:

• '1' and '0' as operands
• '&' (AND) and '|' (OR) as operators
• '(' and ')' for grouping

Each operator works on exactly two operands. The expression is fully parenthesized where needed, so there is no ambiguity.

You can perform two types of operations, each costing 1:

1. Flip a value: change 0 to 1 or 1 to 0
2. Flip an operator: change & to | or | to &

Return the minimum cost to change the final evaluated value of the expression.

Example: "1|(0&0)" evaluates to 1. To flip the result to 0, the minimum cost is 1. You can change the | to &, making the expression "1&(0&0)", which evaluates to 0.

Why this is tricky

The challenge is not just evaluating the expression. You need to know, for every subexpression, how cheaply you can flip its result. And the cost depends on the operator connecting two subexpressions and the flip costs of both children.

Consider 0 & 0. The result is 0. To flip it to 1:

• You could flip both operands to 1 (cost = 2), since 1 & 1 = 1
• Or you could flip the & to | and flip one operand (cost = 1 + 1 = 2)
• Or you could flip the & to | without flipping operands, giving 0 | 0 = 0, which does not help
• The best option: flip just one operand and change & to |, giving 1 | 0 = 1 at cost 2. Or notice that min(costLeft, costRight) = 1 when flipping the operator gives the right structure.

Nested parentheses make this worse. You cannot just greedily pick the cheapest change at the top level because a cheaper option might exist deeper in the tree. You need to propagate costs bottom-up through the entire expression structure.

The approach

Use a stack to parse the expression left to right, just like you would in a basic calculator problem. But instead of tracking a single numeric result, each entry on the stack is a pair: (value, minCostToFlip).

Here is how the stack works:

1. Literal 0 or 1: push (val, 1). The value is the literal, and it costs 1 to flip it.
2. Operator & or |: push it onto the stack.
3. Open paren (: push it as a boundary marker.
4. Close paren ) or second operand encountered: pop the right operand, the operator, and the left operand. Combine them using the DP rules below. Push the result back.

The DP combination rules for left op right:

For AND (&), the result is left_val & right_val:

• If result is 0 (at least one side is 0): to flip to 1, you need both sides to be 1. Cost = min(leftCost, rightCost) if one side is already 1, or leftCost + rightCost if both are 0. But you can also flip the & to | and then just need one side to be 1: cost = 1 + min(costToMakeLeftOne, costToMakeRightOne). Take the minimum.
• If result is 1 (both sides are 1): to flip to 0, you just need one side to become 0. Cost = min(leftCost, rightCost). You could also flip & to |, but 1 | 1 = 1 still, so flipping the operator alone does not help. You would need to flip the operator AND make both sides 0, which costs more.

For OR (|), the result is left_val | right_val:

• If result is 1 (at least one side is 1): to flip to 0, you need both sides to be 0. Similar logic: min(leftCost, rightCost) if one side is already 0, or leftCost + rightCost if both are 1. Alternatively, flip | to & and just need one side to be 0: cost = 1 + min(costToMakeLeftZero, costToMakeRightZero).
• If result is 0 (both sides are 0): to flip to 1, you just need one side to become 1. Cost = min(leftCost, rightCost). Flipping the operator to & gives 0 & 0 = 0, which does not help.

The compact formulas:

• val = 1, op = &: cost = min(c_left, c_right) (flip either side to 0)
• val = 0, op = &, one side is 0: cost = min(c_zero_side, 1 + c_one_side) where flipping operator + keeping the 1 side gives a path
• val = 0, op = &, both sides 0: cost = min(c_left + c_right, 1 + min(c_left, c_right))
• Symmetric rules for |

Visual walkthrough

Let's trace through the expression "1|(0&0)" step by step. The stack holds (value, cost) pairs, operators, and parenthesis markers.

The code

def minOperationsToFlip(expression):
    stack = []

    def combine(left, op, right):
        lv, lc = left
        rv, rc = right
        if op == '&':
            val = lv & rv
            if val == 1:
                cost = min(lc, rc)
            else:
                if lv == 0 and rv == 0:
                    cost = min(lc + rc, 1 + min(lc, rc))
                else:
                    zero_cost = lc if lv == 0 else rc
                    one_cost = rc if lv == 0 else lc
                    cost = min(zero_cost, 1 + one_cost)
        else:
            val = lv | rv
            if val == 0:
                cost = min(lc, rc)
            else:
                if lv == 1 and rv == 1:
                    cost = min(lc + rc, 1 + min(lc, rc))
                else:
                    one_cost = lc if lv == 1 else rc
                    zero_cost = rc if lv == 1 else lc
                    cost = min(one_cost, 1 + zero_cost)
        return (val, cost)

    for ch in expression:
        if ch == '0' or ch == '1':
            val = int(ch)
            entry = (val, 1)
            if len(stack) >= 2 and stack[-1] in ('&', '|') and stack[-2] != '(':
                op = stack.pop()
                left = stack.pop()
                entry = combine(left, op, entry)
            stack.append(entry)
        elif ch == '(' or ch == '&' or ch == '|':
            stack.append(ch)
        elif ch == ')':
            inner = stack.pop()
            stack.pop()
            if len(stack) >= 2 and stack[-1] in ('&', '|') and stack[-2] != '(':
                op = stack.pop()
                left = stack.pop()
                inner = combine(left, op, inner)
            stack.append(inner)

    return stack[0][1]

Let's walk through the key parts:

1. combine(left, op, right) does the DP merge. It takes two (value, cost) pairs and an operator, then returns the combined (value, cost). The logic handles all four cases: AND with result 1, AND with result 0, OR with result 1, OR with result 0.

2. When we read a literal (0 or 1), we create a (val, 1) entry. If the stack already has an operator and a left operand waiting (and we are not inside a new parenthesized group), we immediately combine them. This handles expressions without parentheses around every operator.

3. When we read ), we pop the inner result, discard the matching (, and again check if there is a pending operator to combine with.

4. The answer is stack[0][1], the cost stored in the final remaining entry.

Complexity analysis

The linear time might seem surprising given the DP aspect, but the stack-based approach processes each token exactly once. The combine function does constant work per pair, and each pair is created once and consumed once.

The building blocks

This problem is built on two reusable pieces:

1. Expression parsing with a stack

The stack-based parsing here is the same pattern you see in Basic Calculator and similar problems. Push operands and operators, use parentheses as boundaries, and combine when you have a complete subexpression. The difference is what you store on the stack (a (value, cost) pair instead of a number) and how you combine (DP rules instead of arithmetic).

2. DP on subproblems with two return values

Many tree DP problems require returning more than one value from each subtree. Here, each subexpression returns (value, minCostToFlip). This pattern shows up in problems like Binary Tree Maximum Path Sum (return both the max path through the node and the max path ending at the node) and House Robber III (return the best with and without robbing the current node).

Edge cases

• Single literal like "0" or "1": the answer is always 1. You just flip the value.
• No parentheses like "1|0&1": the expression is still valid and left-to-right association applies. The stack handles this naturally by combining as soon as it has two operands and an operator.
• Deeply nested expression like "((((0)))): each layer of parentheses just wraps the same value. The cost stays 1 regardless of nesting depth.
• All same values with same operator like "1&1&1&1": result is 1, and the cost to flip is 1 (just flip any single operand). The combine step correctly computes min(1, 1) = 1 at each level.

From understanding to recall

This problem combines two patterns that you probably already know individually: stack-based expression parsing and DP with multi-value returns. The hard part is merging them cleanly. The combine function has four cases (two operators, two result values), and each case has its own cost formula involving flipping operands, flipping the operator, or both.

In an interview, the risk is not failing to understand the approach. It is getting the combine logic wrong under pressure. You need to remember which case allows a cheap single flip versus requiring both children to change. Spaced repetition helps here because each practice session forces you to rederive the formulas from the truth tables of AND and OR, building the intuition until it becomes automatic.

Related posts

• Evaluate Reverse Polish Notation - Stack-based expression evaluation
• Longest Valid Parentheses - Stack-based parentheses processing
• Basic Calculator - Another expression parsing problem