LeetCode 2118 - Build the Equation

The problem asks us to construct a polynomial equation from a database table called Terms. Each row in the table represents a single term in the equation, where power is the exponent of X and factor is the coefficient.

leetcodeharddatabase

LeetCode Problem 2118

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem asks us to construct a polynomial equation from a database table called Terms. Each row in the table represents a single term in the equation, where power is the exponent of X and factor is the coefficient. The goal is to output a single string representing the equation, where all terms are concatenated in descending order of their powers, and the right-hand side is always zero.

The output format is very strict: each term must start with a sign (+ or -), followed by the absolute value of the factor, then X raised to the power if the power is greater than 1. If the power is 1, only X appears without the exponent. If the power is 0, only the number appears without X. This requires careful handling of string formatting and ordering.

The input guarantees that factor is non-zero and power is unique, which simplifies the problem. Important edge cases include negative coefficients, powers of 0 or 1, and a table with only one term.

The follow-up, where power may not be unique, would require first summing the coefficients for the same power before constructing the equation string.

Approaches

The brute-force approach is straightforward: read all terms from the table, sort them by descending power, and manually build the string by iterating over each row. Each term requires conditional formatting based on its power. This works because the dataset is small (power ≤ 100), but it does not scale well if additional operations like summing duplicate powers are needed. The brute-force approach is correct but mechanically repetitive.

The optimal approach leverages SQL's string functions along with an ORDER BY clause to sort powers in descending order. For each term, we conditionally format the string depending on the power using CASE statements. This avoids post-processing in application code and ensures the string is built directly in the database query. It is more elegant and scales better with the number of terms.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Sort in application and format each term manually
Optimal O(n log n) O(1) Sort in SQL and build string using aggregation and CASE

Algorithm Walkthrough

  1. Start by reading all rows from the Terms table.
  2. Sort the rows in descending order of power.
  3. For each term, determine the string representation based on power:
  • If power = 0, append +factor or -factor.
  • If power = 1, append +factorX or -factorX.
  • Otherwise, append +factorX^power or -factorX^power.
  1. Use the absolute value of the factor when writing the term, but prepend the sign based on the original factor.
  2. Concatenate all formatted terms into a single string.
  3. Append =0 at the end to complete the equation.
  4. Return the resulting string as a single column named equation.

Why it works: By sorting powers in descending order and formatting each term correctly, we maintain the correct order and mathematical representation of the polynomial. Using the absolute value of the factor with the sign ensures that both positive and negative terms are represented correctly.

Python Solution

import sqlite3
from typing import List, Tuple

def buildEquation(terms: List[Tuple[int, int]]) -> str:
    # Sort terms in descending order of power
    terms.sort(key=lambda x: -x[0])
    
    equation_parts = []
    for power, factor in terms:
        sign = '+' if factor > 0 else '-'
        abs_factor = abs(factor)
        
        if power == 0:
            term_str = f"{sign}{abs_factor}"
        elif power == 1:
            term_str = f"{sign}{abs_factor}X"
        else:
            term_str = f"{sign}{abs_factor}X^{power}"
        
        equation_parts.append(term_str)
    
    return ''.join(equation_parts) + '=0'

The code first sorts the list of tuples in descending order of powers. Then, for each term, it constructs the string based on the power. The sign is determined from the factor, and the absolute value is used in the string. Finally, all strings are concatenated and =0 is appended to form the complete equation.

Go Solution

package main

import (
    "fmt"
    "sort"
    "strconv"
)

type Term struct {
    Power  int
    Factor int
}

func buildEquation(terms []Term) string {
    sort.Slice(terms, func(i, j int) bool {
        return terms[i].Power > terms[j].Power
    })
    
    equation := ""
    for _, term := range terms {
        sign := "+"
        if term.Factor < 0 {
            sign = "-"
        }
        absFactor := term.Factor
        if absFactor < 0 {
            absFactor = -absFactor
        }
        
        var part string
        if term.Power == 0 {
            part = fmt.Sprintf("%s%d", sign, absFactor)
        } else if term.Power == 1 {
            part = fmt.Sprintf("%s%dX", sign, absFactor)
        } else {
            part = fmt.Sprintf("%s%dX^%d", sign, absFactor, term.Power)
        }
        equation += part
    }
    equation += "=0"
    return equation
}

The Go implementation mirrors Python. We sort the slice of terms by descending power, determine the sign and absolute value, then construct the formatted string using fmt.Sprintf. Finally, we concatenate all parts and append =0.

Worked Examples

Example 1:

Input: [(2, 1), (1, -4), (0, 2)]

Sorted by power: [(2,1),(1,-4),(0,2)]

Power Factor Sign Term String
2 1 + +1X^2
1 -4 - -4X
0 2 + +2

Concatenated string: +1X^2-4X+2=0

Example 2:

Input: [(4, -4), (2, 1), (1, -1)]

Sorted by power: [(4,-4),(2,1),(1,-1)]

Power Factor Sign Term String
4 -4 - -4X^4
2 1 + +1X^2
1 -1 - -1X

Concatenated string: -4X^4+1X^2-1X=0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting terms by power dominates the complexity
Space O(n) Storing formatted strings in a list before joining

The sorting step requires O(n log n), while building the string requires a single pass over the list O(n).

Test Cases

# Provided examples
assert buildEquation([(2,1),(1,-4),(0,2)]) == "+1X^2-4X+2=0"
assert buildEquation([(4,-4),(2,1),(1,-1)]) == "-4X^4+1X^2-1X=0"

# Single term
assert buildEquation([(0,5)]) == "+5=0"
assert buildEquation([(1,-3)]) == "-3X=0"

# Negative factors
assert buildEquation([(3,-2),(0,-1)]) == "-2X^3-1=0"

# Mixed powers and factors
assert buildEquation([(2,3),(1,4),(0,-5)]) == "+3X^2+4X-5=0"

# Powers not in order
assert buildEquation([(0,1),(3,-2),(1,3)]) == "-2X^3+3X+1=0"
Test Why
Provided examples Validates standard case handling
Single term Ensures formatting works with only one term
Negative factors Checks correct handling of negative numbers
Mixed powers and factors Validates correct concatenation order and signs
Powers not in order Ensures sorting is applied before formatting

Edge Cases

One edge case is when the polynomial has only one term. The algorithm correctly adds the sign and =0 regardless of the term's power. Another edge case is when the power is 0 or 1, which requires conditional formatting to avoid adding X or ^1 incorrectly. A third edge case is negative coefficients, which must prepend - and use the absolute value in the term string. The algorithm handles this consistently by checking the sign and using abs() or equivalent logic.