LeetCode 2990 - Loan Types

LeetCode Problem 2990

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem requires identifying users who have taken both a "Refinance" loan and a "Mortgage" loan. The input is a table Loans containing loan_id, user_id, and loan_type. Each row represents one loan taken by a user, and loan_id is unique. We are asked to return a list of distinct user_id values who satisfy the condition of having at least one loan of each of the two specified types, ordered by user_id in ascending order.

Key points are: the table may contain multiple loans per user, including different types, and the query must only return users meeting both conditions. The problem guarantees unique loan_id values but does not limit the number of users or loans per user. Edge cases to consider include users with multiple loans of the same type, users with only one type, and an empty table.

Approaches

A brute-force approach would scan the Loans table, maintaining for each user a list of loan types they have. After building this map, we could iterate through it and select users who have both "Refinance" and "Mortgage" in their list. While correct, this requires extra memory to store all loan types per user and involves multiple iterations, making it less efficient for large datasets.

The optimal approach uses SQL aggregation to identify users meeting both criteria in a single query. By grouping the table by user_id and counting distinct occurrences of "Refinance" and "Mortgage", we can filter groups where both counts are at least one. This leverages the database engine's optimizations for grouping and filtering, avoiding the need for additional in-memory data structures.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(u * t)	Build map of loan types per user, then filter
Optimal	O(n)	O(u)	Use GROUP BY and HAVING to filter in SQL efficiently

Where n is the number of loans, u is the number of unique users, and t is the average number of loan types per user.

Algorithm Walkthrough

1. Start by grouping the Loans table by user_id. This ensures that all loans for a given user are aggregated together.
2. For each group, count how many loans are of type "Refinance" and how many are of type "Mortgage". Use conditional aggregation to compute these counts efficiently.
3. Use a HAVING clause to filter groups where both counts are at least 1. This guarantees that only users who have both types of loans remain.
4. Select only the user_id column from the filtered results.
5. Order the result by user_id in ascending order to meet the output requirement.

Why it works: Grouping by user_id ensures we consider all loans for each user collectively. The conditional counts confirm whether the user satisfies both loan conditions. Filtering via HAVING ensures correctness and efficiency.

Python Solution

Since this is a database problem, the Python solution uses a SQL execution framework. For the sake of completeness, a Python example using a query execution is shown.

def find_users_with_loans(cursor) -> list[int]:
    query = """
    SELECT user_id
    FROM Loans
    GROUP BY user_id
    HAVING SUM(CASE WHEN loan_type = 'Refinance' THEN 1 ELSE 0 END) > 0
       AND SUM(CASE WHEN loan_type = 'Mortgage' THEN 1 ELSE 0 END) > 0
    ORDER BY user_id ASC;
    """
    cursor.execute(query)
    return [row[0] for row in cursor.fetchall()]

This code executes a single SQL query using a database cursor, retrieving the filtered user_ids and returning them as a list of integers.

Go Solution

In Go, the same SQL query can be executed using the database/sql package:

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
)

func FindUsersWithLoans(db *sql.DB) ([]int, error) {
    query := `
    SELECT user_id
    FROM Loans
    GROUP BY user_id
    HAVING SUM(CASE WHEN loan_type = 'Refinance' THEN 1 ELSE 0 END) > 0
       AND SUM(CASE WHEN loan_type = 'Mortgage' THEN 1 ELSE 0 END) > 0
    ORDER BY user_id ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var userIDs []int
    for rows.Next() {
        var userID int
        if err := rows.Scan(&userID); err != nil {
            return nil, err
        }
        userIDs = append(userIDs, userID)
    }
    return userIDs, nil
}

Go handles database rows iteratively, appending each user_id to a slice, which mirrors the Python approach.

Worked Examples

Using the provided example table:

+---------+---------+-----------+
| loan_id | user_id | loan_type |
+---------+---------+-----------+
| 683     | 101     | Mortgage  |
| 218     | 101     | AutoLoan  |
| 802     | 101     | Inschool  |
| 593     | 102     | Mortgage  |
| 138     | 102     | Refinance |
| 294     | 102     | Inschool  |
| 308     | 103     | Refinance |
| 389     | 104     | Mortgage  |
+---------+---------+-----------+

Step by step:

1. Group loans by user_id:

101 → Mortgage, AutoLoan, Inschool

102 → Mortgage, Refinance, Inschool

103 → Refinance

104 → Mortgage 2. Conditional counts:

101 → Refinance=0, Mortgage=1 → excluded

102 → Refinance=1, Mortgage=1 → included

103 → Refinance=1, Mortgage=0 → excluded

104 → Refinance=0, Mortgage=1 → excluded 3. Filter by having both counts > 0 → only 102 remains. 4. Return [102].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each row is scanned once for grouping and counting
Space	O(u)	Stores counts per user, where u is number of unique users

The algorithm is linear with respect to the number of loans, and uses minimal additional memory proportional to the number of users.

Test Cases

# test cases
# single qualifying user
assert find_users_with_loans(cursor) == [102]  # example from problem

# multiple qualifying users
# user 201 and 202 both have Mortgage and Refinance
assert find_users_with_loans(cursor) == [201, 202]

# no qualifying users
assert find_users_with_loans(cursor) == []

# users with multiple loans of same type
# user 301 has 2 Mortgages, 1 Refinance → qualifies
assert find_users_with_loans(cursor) == [301]

# empty table
assert find_users_with_loans(cursor) == []

Test	Why
example from problem	Validates basic functionality
multiple qualifying users	Confirms algorithm handles multiple results
no qualifying users	Ensures empty output is correct
multiple loans same type	Confirms counting logic handles duplicates
empty table	Confirms code handles no input

Edge Cases

A critical edge case is a user with multiple loans of the same type but missing the other required type. Naive implementations may incorrectly count total loans instead of specific types; the conditional aggregation ensures only relevant types are counted.

Another edge case is an empty Loans table. The algorithm correctly returns an empty result without error.

Finally, users with only one of the two required loan types must be excluded. Grouping and conditional counts ensure that only users meeting both conditions are included, regardless of how many additional loan types they have.