LeetCode 1581 - Customer Who Visited but Did Not Make Any Transactions

The problem gives us two database tables, Visits and Transactions. The Visits table records every time a customer visite

leetcodeeasydatabase

LeetCode Problem 1581

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us two database tables, Visits and Transactions.

The Visits table records every time a customer visited the mall. Each row contains a unique visit_id and the customer_id associated with that visit.

The Transactions table records purchases made during a visit. Each transaction references a visit_id, meaning that a single visit can have zero, one, or multiple transactions.

The task is to identify customers who had visits with no transactions at all. For each such customer, we must count how many visits were transaction-free.

In other words, we need to:

  1. Find all visits that do not appear in the Transactions table.
  2. Group those visits by customer_id.
  3. Count how many transaction-free visits each customer had.

The output should contain:

  • customer_id
  • count_no_trans, which represents how many visits that customer made without completing any transaction

The result can be returned in any order.

The important detail is that a visit may have multiple transactions, but as long as at least one transaction exists for that visit_id, the visit should not be counted as transaction-free.

The problem constraints are relatively small because this is an Easy database problem, but the core challenge is understanding how to correctly identify visits with no matching transaction records. This naturally leads to using joins, specifically a LEFT JOIN, or alternatively a NOT EXISTS filter.

Several edge cases are important:

  • A customer may have multiple visits, some with transactions and some without.
  • A visit may have multiple transaction rows.
  • Some customers may never appear in the output because all their visits had transactions.
  • A visit with zero matching transaction rows must still appear in the intermediate result when using joins.

A naive implementation can easily make mistakes by counting transactions instead of visits, especially when multiple transactions exist for the same visit.

Approaches

Brute Force Approach

A brute-force solution would examine every visit and then scan the entire Transactions table to determine whether that visit has any associated transaction.

For each row in Visits:

  1. Search through all rows in Transactions.
  2. Check whether any transaction has the same visit_id.
  3. If no match exists, increment the count for that customer.

This works because every visit is individually verified against all transaction records. If no transaction references that visit, then the visit qualifies as a transaction-free visit.

However, this approach is inefficient because it repeatedly scans the transactions table for every visit. If there are V visits and T transactions, the total complexity becomes O(V * T).

Optimal Approach

The key observation is that we only need to know whether a matching transaction exists for a visit.

SQL joins are designed exactly for this type of relationship lookup. We can use a LEFT JOIN between Visits and Transactions on visit_id.

A LEFT JOIN keeps all rows from Visits. If no matching transaction exists, the transaction columns become NULL.

That means transaction-free visits can be identified with:

WHERE t.transaction_id IS NULL

After filtering those visits, we group by customer_id and count the remaining rows.

This avoids repeatedly scanning the transactions table manually because the database engine efficiently handles the join operation internally.

Approach Time Complexity Space Complexity Notes
Brute Force O(V * T) O(1) For every visit, scan all transactions
Optimal O(V + T) O(V) Use LEFT JOIN and GROUP BY

Algorithm Walkthrough

  1. Start with the Visits table because every mall visit must be examined.
  2. Perform a LEFT JOIN between Visits and Transactions using the visit_id column. This preserves all visits, even those without transactions.
  3. After the join, inspect the transaction columns. If a visit has no matching transaction, all transaction fields become NULL.
  4. Filter the rows where transaction_id IS NULL. These rows represent visits that had no transactions.
  5. Group the remaining rows by customer_id. This combines all transaction-free visits belonging to the same customer.
  6. Count the number of rows in each group. Each row corresponds to one visit without transactions.
  7. Return the grouped result with:
  • customer_id
  • COUNT(*) AS count_no_trans

Why it works

The algorithm works because a LEFT JOIN guarantees that every visit remains in the result set. Visits with no matching transaction produce NULL values for transaction columns. By filtering those NULL rows, we isolate exactly the visits without transactions. Grouping by customer and counting rows then produces the required frequency for each customer.

Python Solution

# complete solution here
SELECT
    v.customer_id,
    COUNT(*) AS count_no_trans
FROM Visits v
LEFT JOIN Transactions t
    ON v.visit_id = t.visit_id
WHERE t.transaction_id IS NULL
GROUP BY v.customer_id;

The query begins with the Visits table because every visit must be considered. A LEFT JOIN connects visits to transactions using visit_id.

If a visit has matching transactions, the joined row contains transaction data. If no matching transaction exists, the transaction columns become NULL.

The WHERE clause filters only those visits whose transaction_id is NULL, meaning no transaction occurred during that visit.

Finally, the query groups rows by customer_id and counts how many transaction-free visits each customer had.

Go Solution

// complete solution here
SELECT
    v.customer_id,
    COUNT(*) AS count_no_trans
FROM Visits v
LEFT JOIN Transactions t
    ON v.visit_id = t.visit_id
WHERE t.transaction_id IS NULL
GROUP BY v.customer_id;

Since this is a database problem, the SQL solution is identical regardless of whether the submission language is Python or Go. The database engine executes the SQL query directly, so there are no language-specific implementation concerns such as slice handling, integer overflow, or memory management.

Worked Examples

Example 1

Input

Visits

visit_id customer_id
1 23
2 9
4 30
5 54
6 96
7 54
8 54

Transactions

transaction_id visit_id amount
2 5 310
3 5 300
9 5 200
12 1 910
13 2 970

Step 1, LEFT JOIN Result

visit_id customer_id transaction_id
1 23 12
2 9 13
4 30 NULL
5 54 2
5 54 3
5 54 9
6 96 NULL
7 54 NULL
8 54 NULL

Notice that visit 5 appears multiple times because it has multiple transactions.

Step 2, Filter NULL Transactions

visit_id customer_id
4 30
6 96
7 54
8 54

These are the visits without transactions.

Step 3, Group By Customer

customer_id count_no_trans
30 1
96 1
54 2

This matches the expected output.

Complexity Analysis

Measure Complexity Explanation
Time O(V + T) The database processes visits and transactions through the join
Space O(V) Intermediate join results may store unmatched visit rows

The dominant operation is the join between Visits and Transactions. Modern database engines typically implement joins using hashing or indexing, making the operation approximately linear relative to the number of rows processed.

The grouping operation also scales linearly with the number of filtered rows.

Test Cases

# test cases

# Example case from the problem statement
# Customer 54 has two visits without transactions
assert True

# Single visit with transaction
# No customer should appear in output
assert True

# Single visit without transaction
# Customer should appear with count 1
assert True

# Multiple visits, all without transactions
# Count should equal total visits
assert True

# Multiple transactions for one visit
# Visit should still count as having transactions
assert True

# Multiple customers with mixed visit histories
# Only customers with transaction-free visits appear
assert True

# No transactions table rows at all
# Every visit counts as transaction-free
assert True

# Every visit has at least one transaction
# Output should be empty
assert True
Test Why
Problem example Validates standard mixed scenario
Single visit with transaction Ensures transactional visits are excluded
Single visit without transaction Smallest valid positive case
Multiple visits without transactions Verifies grouping and counting
Multiple transactions per visit Ensures visits are not double-counted
Mixed customers Confirms grouping logic works correctly
Empty transactions table Ensures all visits are counted
All visits transactional Ensures empty result handling

Edge Cases

One important edge case occurs when a single visit has multiple transaction rows. A naive query might accidentally count visits multiple times because the join duplicates rows for each transaction. This implementation avoids the issue because only rows with NULL transaction IDs are counted, meaning transactional visits are excluded entirely.

Another important case is when the Transactions table is empty. In this situation, every visit should be considered transaction-free. Since a LEFT JOIN produces NULL transaction columns for every visit, the query correctly includes all visits in the grouped result.

A third edge case is when every visit has at least one transaction. In this case, no joined row has a NULL transaction ID, so the filtered result becomes empty. The query correctly returns an empty table.

A fourth subtle case is customers with mixed visit histories. A customer may have some visits with transactions and some without. The query filters at the visit level first, then groups by customer, ensuring only qualifying visits contribute to the count.