LeetCode 1440 - Evaluate Boolean Expression

This problem asks us to evaluate boolean expressions stored in a database table. We are given two tables: Variables, whi

leetcodemediumdatabase

LeetCode Problem 1440

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to evaluate boolean expressions stored in a database table. We are given two tables: Variables, which stores variable names and their corresponding integer values, and Expressions, which stores boolean expressions made up of two operands and a comparison operator.

Each row in Expressions represents a condition of the form:

left_operand operator right_operand

For example:

x > y

The operands are variable names, not raw numbers. Their actual integer values must be looked up from the Variables table. After retrieving the values, we evaluate the expression using the given operator, which can only be one of:

  • <
  • >
  • =

The task is to return a result table containing all original expression columns along with a new column called value, which indicates whether the expression evaluates to true or false.

For example, if:

x = 66
y = 77

then:

x < y

becomes:

66 < 77

which evaluates to true.

The key observation is that expressions reference variable names, not their actual numeric values. Therefore, before evaluating any expression, we must join each operand to the Variables table to retrieve its integer value.

The problem guarantees that every operand appearing in Expressions exists in the Variables table. This means we never need to handle missing variables or null lookups. Additionally, the operator is restricted to only three valid comparison operators, so the evaluation logic remains straightforward.

An important edge case is when both operands are the same variable, such as:

x = x

In this case, the expression must evaluate using the same value on both sides. Another edge case involves equal numeric values between different variables, where < and > become false while = becomes true. A naive implementation could also fail if it repeatedly scans the Variables table for every expression instead of efficiently matching values through joins.

Approaches

Brute Force Approach

A brute-force solution would evaluate each expression by repeatedly scanning the Variables table to locate the values for both operands.

For every row in Expressions, we would:

  1. Search Variables to find the value of left_operand
  2. Search Variables again to find the value of right_operand
  3. Apply the operator to compare the two values
  4. Store the boolean result

This approach works because every expression is independently evaluated using the correct variable values. However, it is inefficient because each expression requires multiple scans through Variables.

If there are E expressions and V variables, then for every expression we potentially scan all variables twice, producing a time complexity of O(E × V).

Optimal Approach

The key insight is that relational databases are designed for matching related rows efficiently using joins.

Instead of repeatedly searching for operand values, we can join the Expressions table with Variables twice:

  • Once to retrieve the value of left_operand
  • Once to retrieve the value of right_operand

After obtaining both numeric values, we use a CASE statement to evaluate the expression based on the operator.

This works efficiently because joins allow us to directly match variable names to values without repeated scanning logic.

Approach Time Complexity Space Complexity Notes
Brute Force O(E × V) O(1) Repeatedly scans variables for every expression
Optimal O(E + V) O(1) Uses joins to efficiently retrieve operand values

Algorithm Walkthrough

  1. Start with the Expressions table because each row represents a boolean expression we must evaluate.
  2. Join the Variables table for the left operand. We match:
Expressions.left_operand = Variables.name

This gives us the numeric value of the left side. 3. Join the Variables table a second time for the right operand. Since we need values for both operands independently, we use a different alias:

Expressions.right_operand = Variables.name

Now we have both operand values available. 4. Use a CASE expression to evaluate the operator. Since the operator can only be <, >, or =, we check which operator appears and apply the corresponding comparison. 5. Return the original expression columns plus the evaluated boolean result as the value column.

Why it works

The algorithm works because every operand is guaranteed to exist in Variables, meaning each join always produces a valid numeric value. By joining twice, we retrieve the exact values for both operands, and the CASE statement evaluates the correct comparison based on the operator. Since each expression is processed independently and every operator is handled explicitly, the output is guaranteed to be correct.

Python Solution

Although this is a database problem and LeetCode expects an SQL query instead of Python code, the following demonstrates the equivalent logic programmatically.

from typing import List, Dict

class Solution:
    def evaluateExpressions(
        self,
        variables: List[List[str]],
        expressions: List[List[str]]
    ) -> List[List[str]]:
        variable_map: Dict[str, int] = {
            name: value
            for name, value in variables
        }

        result = []

        for left_operand, operator, right_operand in expressions:
            left_value = variable_map[left_operand]
            right_value = variable_map[right_operand]

            if operator == "<":
                value = left_value < right_value
            elif operator == ">":
                value = left_value > right_value
            else:
                value = left_value == right_value

            result.append([
                left_operand,
                operator,
                right_operand,
                str(value).lower()
            ])

        return result

The implementation begins by converting the Variables table into a hash map. This allows constant time lookup of any variable's numeric value. Without this preprocessing step, we would repeatedly scan the variables list for every expression.

Next, we iterate through every expression. For each expression, we retrieve the numeric values of both operands from the hash map. Once we have the numbers, we apply the operator using standard comparison logic.

Finally, we append the evaluated result to the output list while preserving the original expression structure.

SQL Solution for LeetCode

This is the actual query expected by LeetCode:

SELECT
    e.left_operand,
    e.operator,
    e.right_operand,
    CASE
        WHEN e.operator = '>' THEN v1.value > v2.value
        WHEN e.operator = '<' THEN v1.value < v2.value
        ELSE v1.value = v2.value
    END AS value
FROM Expressions e
JOIN Variables v1
    ON e.left_operand = v1.name
JOIN Variables v2
    ON e.right_operand = v2.name;

This query performs two joins to retrieve operand values and then evaluates the expression using a CASE statement.

Go Solution

Again, this problem is SQL-based, but here is an equivalent implementation in Go.

package main

type Solution struct{}

func (s Solution) EvaluateExpressions(
	variables [][]interface{},
	expressions [][]string,
) [][]string {

	variableMap := make(map[string]int)

	for _, variable := range variables {
		name := variable[0].(string)
		value := variable[1].(int)
		variableMap[name] = value
	}

	result := [][]string{}

	for _, expression := range expressions {
		leftOperand := expression[0]
		operator := expression[1]
		rightOperand := expression[2]

		leftValue := variableMap[leftOperand]
		rightValue := variableMap[rightOperand]

		value := false

		if operator == "<" {
			value = leftValue < rightValue
		} else if operator == ">" {
			value = leftValue > rightValue
		} else {
			value = leftValue == rightValue
		}

		boolString := "false"
		if value {
			boolString = "true"
		}

		result = append(result, []string{
			leftOperand,
			operator,
			rightOperand,
			boolString,
		})
	}

	return result
}

The Go implementation closely mirrors the Python solution. A map[string]int is used for constant time variable lookup. Since Go does not have Python-style dynamic typing, we explicitly cast values when reading input data. Boolean values are converted into "true" or "false" strings before insertion into the result.

Worked Examples

Example 1

Variables Table

Variable Value
x 66
y 77

We first build the lookup map:

{
    "x": 66,
    "y": 77
}

Now evaluate each expression.

Expression Left Value Right Value Evaluation Result
x > y 66 77 66 > 77 false
x < y 66 77 66 < 77 true
x = y 66 77 66 == 77 false
y > x 77 66 77 > 66 true
y < x 77 66 77 < 66 false
x = x 66 66 66 == 66 true

Final output:

left_operand operator right_operand value
x > y false
x < y true
x = y false
y > x true
y < x false
x = x true

Complexity Analysis

Measure Complexity Explanation
Time O(E + V) Building the variable lookup costs O(V), evaluating all expressions costs O(E)
Space O(V) The hash map stores all variables

The algorithm is efficient because each variable is inserted into the lookup structure exactly once, and each expression is evaluated exactly once. Since hash map lookups are constant time on average, the overall complexity grows linearly with the input size.

For the SQL solution, join performance depends on indexing, but conceptually the database processes each row efficiently through relational joins.

Test Cases

def evaluate_expressions(variables, expressions):
    variable_map = {
        name: value
        for name, value in variables
    }

    result = []

    for left, operator, right in expressions:
        left_value = variable_map[left]
        right_value = variable_map[right]

        if operator == "<":
            value = left_value < right_value
        elif operator == ">":
            value = left_value > right_value
        else:
            value = left_value == right_value

        result.append(
            [left, operator, right, str(value).lower()]
        )

    return result

# Provided example
assert evaluate_expressions(
    [["x", 66], ["y", 77]],
    [
        ["x", ">", "y"],
        ["x", "<", "y"],
        ["x", "=", "y"],
        ["y", ">", "x"],
        ["y", "<", "x"],
        ["x", "=", "x"]
    ]
) == [
    ["x", ">", "y", "false"],
    ["x", "<", "y", "true"],
    ["x", "=", "y", "false"],
    ["y", ">", "x", "true"],
    ["y", "<", "x", "false"],
    ["x", "=", "x", "true"]
]  # Problem statement example

# Same value comparison
assert evaluate_expressions(
    [["a", 10], ["b", 10]],
    [["a", "=", "b"]]
) == [
    ["a", "=", "b", "true"]
]  # Equal values across different variables

# Self comparison
assert evaluate_expressions(
    [["x", 5]],
    [["x", "=", "x"]]
) == [
    ["x", "=", "x", "true"]
]  # Variable compared with itself

# Less than comparison
assert evaluate_expressions(
    [["a", 1], ["b", 2]],
    [["a", "<", "b"]]
) == [
    ["a", "<", "b", "true"]
]  # Basic less-than evaluation

# Greater than comparison
assert evaluate_expressions(
    [["a", 5], ["b", 2]],
    [["a", ">", "b"]]
) == [
    ["a", ">", "b", "true"]
]  # Basic greater-than evaluation
Test Why
Example from prompt Verifies standard functionality
Equal values across variables Ensures = works for different variables
Self comparison Verifies same variable on both sides
Basic < comparison Tests less-than logic
Basic > comparison Tests greater-than logic

Edge Cases

Comparing a Variable With Itself

An expression such as:

x = x

can expose bugs if the implementation incorrectly assumes operands are always different. Since both operands refer to the same variable, both lookups should retrieve the exact same value. Our implementation handles this naturally because both operand names are independently resolved through the lookup structure or joins.

Different Variables With Equal Values

Two different variable names may store identical numeric values:

a = 10
b = 10

In this case:

a = b

should evaluate to true, while:

a > b

and:

a < b

should both evaluate to false. The implementation avoids mistakes here because comparisons are based entirely on numeric values, not variable names.

Large Numbers of Expressions

A naive implementation that repeatedly scans the Variables table for every expression would become inefficient as the number of expressions grows. The optimal approach avoids this issue by using joins in SQL or a hash map in code, ensuring each lookup remains constant time and keeping total work linear.