Evaluate Boolean Expression - Solution & Explanation
Problem Statement
Table Variables:
+---------------+---------+ | Column Name | Type | +---------------+---------+ | name | varchar | | value | int | +---------------+---------+ In SQL, name is the primary key for this table. This table contains the stored variables and their values.
Table Expressions:
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| left_operand | varchar |
| operator | enum |
| right_operand | varchar |
+---------------+---------+
In SQL, (left_operand, operator, right_operand) is the primary key for this table.
This table contains a boolean expression that should be evaluated.
operator is an enum that takes one of the values ('<', '>', '=')
The values of left_operand and right_operand are guaranteed to be in the Variables table.
Evaluate the boolean expressions in Expressions table.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Variables table: +------+-------+ | name | value | +------+-------+ | x | 66 | | y | 77 | +------+-------+ Expressions table: +--------------+----------+---------------+ | left_operand | operator | right_operand | +--------------+----------+---------------+ | x | > | y | | x | < | y | | x | = | y | | y | > | x | | y | < | x | | x | = | x | +--------------+----------+---------------+ 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 | +--------------+----------+---------------+-------+ Explanation: As shown, you need to find the value of each boolean expression in the table using the variables table.
Approach Overview
Problem Overview: Each row in the Expressions table stores a boolean comparison such as x > y or a = b. The operands reference variable names whose numeric values live in the Variables table. Your task is to evaluate every expression by resolving both operands and returning whether the comparison is true or false.
Approach 1: Equi-Join + CASE Expression (O(n), O(1))
The core idea is to replace variable names with their actual numeric values before evaluating the operator. You achieve this by joining the Expressions table with the Variables table twice: once for the left_operand and once for the right_operand. These are standard equi-joins where Expressions.left_operand = Variables.name and Expressions.right_operand = Variables.name. Each join resolves a variable reference into its numeric value.
After both operands are resolved, evaluate the comparison using a CASE expression. The CASE block checks the operator column (>, <, or =) and performs the corresponding comparison between the joined values. For example, when the operator is '>', compare left_value > right_value. SQL returns the final result as 'true' or 'false' depending on whether the condition holds.
This approach works because SQL joins effectively transform symbolic operands into actual numbers before evaluation. The database engine scans the Expressions rows once and resolves both operands through indexed lookups in the variables table. With proper indexing on Variables.name, the join remains efficient and scales well for larger datasets.
Time complexity is O(n) where n is the number of expressions, assuming indexed lookups for variable names. Each expression requires two joins and a constant-time comparison. Space complexity is O(1) beyond the query result since the database processes rows in a streaming fashion.
This problem primarily tests your understanding of database query composition, multi-table lookups with joins, and conditional evaluation using SQL expressions. The trick is recognizing that the operands are not values yet—they must first be resolved through joins.
Recommended for interviews: The equi-join plus CASE expression solution is the expected approach. It demonstrates that you understand relational lookups and conditional logic in SQL. A naive solution using repeated subqueries works but is less efficient and harder to read. Interviewers typically look for the clean join-based query because it mirrors how relational databases are designed to evaluate cross-table relationships.
Solution
We can associate each row in the Expressions table with two rows in the Variables table using an equi-join, where the conditions for the association are left_operand = name and right_operand = name. Then, we can use a CASE expression to determine the value of the boolean expression. If the operator is =, we check if the two values are equal. If the operator is >, we check if the left value is greater than the right value. If the operator is <, we check if the left value is less than the right value. If the condition is true, the boolean expression evaluates to true, otherwise it evaluates to false.
Code
MySQL
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Equi-Join + CASE Expression | O(n) | O(1) | Best general solution. Efficient when variables table can be joined directly using indexed lookups. |
| Subquery Lookup + CASE | O(n) | O(1) | Simpler to write conceptually but less efficient and less readable due to repeated subqueries for operand values. |
Video Solution
Beyond Basics: 50 Advanced SQL Questions for In-Depth Understanding! - Leetcode 1440 | Data Science • Everyday Data Science • 2,821 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Evaluate Boolean Expression easy or hard?
Evaluate Boolean Expression Python/Java solution
How to solve Evaluate Boolean Expression in O(n)?
What is the best approach for Evaluate Boolean Expression?
Is Evaluate Boolean Expression asked at Google/Amazon/Meta?
What data structure is used in Evaluate Boolean Expression?
What is the time complexity of Evaluate Boolean Expression?
Ready to solve this problem?
Practice Evaluate Boolean Expression with our built-in code editor and test cases.
Practice on FleetCode