Form a Chemical Bond

Problem

Table: Elements

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| symbol      | varchar |
| type        | enum    |
| electrons   | int     |
+-------------+---------+
symbol is the primary key (column with unique values) for this table.
Each row of this table contains information of one element.
type is an ENUM (category) of type ('Metal', 'Nonmetal', 'Noble')
 - If type is Noble, electrons is 0.
 - If type is Metal, electrons is the number of electrons that one atom of this element can give.
 - If type is Nonmetal, electrons is the number of electrons that one atom of this element needs.

Two elements can form a bond if one of them is 'Metal' and the other is 'Nonmetal'.

Write a solution to find all the pairs of elements that can form a bond.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


Input: 
Elements table:
+--------+----------+-----------+
| symbol | type     | electrons |
+--------+----------+-----------+
| He     | Noble    | 0         |
| Na     | Metal    | 1         |
| Ca     | Metal    | 2         |
| La     | Metal    | 3         |
| Cl     | Nonmetal | 1         |
| O      | Nonmetal | 2         |
| N      | Nonmetal | 3         |
+--------+----------+-----------+
Output: 
+-------+----------+
| metal | nonmetal |
+-------+----------+
| La    | Cl       |
| Ca    | Cl       |
| Na    | Cl       |
| La    | O        |
| Ca    | O        |
| Na    | O        |
| La    | N        |
| Ca    | N        |
| Na    | N        |
+-------+----------+
Explanation: 
Metal elements are La, Ca, and Na.
Nonmeal elements are Cl, O, and N.
Each Metal element pairs with a Nonmetal element in the output table.

Solution

Method 1 – Self Join and Filtering

Intuition

A chemical bond can be formed between a metal and a nonmetal if the number of electrons given by the metal equals the number needed by the nonmetal. We can use a self join to pair metals and nonmetals and filter by their electron counts.

Approach

Select all pairs of elements where one is a metal and the other is a nonmetal.
Ensure the number of electrons given by the metal equals the number needed by the nonmetal.
Output the metal and nonmetal symbol pairs.
Order the result by metal symbol and nonmetal symbol.

Code

1
2
3
4
5
6


SELECT m.symbol AS metal, n.symbol AS nonmetal
FROM Elements m
JOIN Elements n
  ON m.type = 'Metal' AND n.type = 'Nonmetal'
  AND m.electrons = n.electrons
ORDER BY m.symbol, n.symbol;

1
2
3
4
5
6


SELECT m.symbol AS metal, n.symbol AS nonmetal
FROM Elements m
JOIN Elements n
  ON m.type = 'Metal' AND n.type = 'Nonmetal'
  AND m.electrons = n.electrons
ORDER BY m.symbol, n.symbol;

1
2
3
4
5
6
7
8


class Solution:
    def form_chemical_bond(self, elements: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        metals = elements[elements['type'] == 'Metal']
        nonmetals = elements[elements['type'] == 'Nonmetal']
        merged = metals.merge(nonmetals, left_on='electrons', right_on='electrons', suffixes=('_m', '_n'))
        result = merged[['symbol_m', 'symbol_n']].rename(columns={'symbol_m': 'metal', 'symbol_n': 'nonmetal'})
        return result.sort_values(['metal', 'nonmetal']).reset_index(drop=True)

Complexity

⏰ Time complexity: O(m * n), where m is the number of metals and n is the number of nonmetals, due to the join operation.
🧺 Space complexity: O(m * n) for storing the join result.

Problem#

Examples#

Solution#

Method 1 – Self Join and Filtering#

Intuition#

Approach#

Code#

Complexity#