LeetCode 1843 - Suspicious Bank Accounts

This problem asks us to identify bank accounts whose monthly income exceeds a predefined limit for at least two consecutive months. We are given two tables: The Accounts table stores the maximum allowed monthly income for each account.

leetcodemediumdatabase

LeetCode Problem 1843

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to identify bank accounts whose monthly income exceeds a predefined limit for at least two consecutive months.

We are given two tables:

The Accounts table stores the maximum allowed monthly income for each account. Every account has exactly one max_income value.

The Transactions table stores individual banking transactions. Each transaction belongs to an account and has:

  • a transaction type,
  • an amount,
  • and a timestamp.

Only transactions with type 'Creditor' count as income. Transactions with type 'Debtor' represent withdrawals and must be ignored for income calculations.

The task is to compute the total deposited amount for each account in every month. Then, for each account, we must determine whether there exist at least two consecutive months where:

monthly_income > max_income

If such consecutive months exist, the account is considered suspicious and should be included in the result.

The result can be returned in any order.

A very important detail is that the months must be consecutive in calendar order, not merely adjacent rows in the dataset. For example:

  • May and June are consecutive.
  • June and July are consecutive.
  • May and July are not consecutive because June is missing.

Another important detail is that equality does not count. The condition explicitly says the income must exceed the limit, so:

monthly_income > max_income

is valid, while:

monthly_income == max_income

is not.

The problem is fundamentally a grouping and sequence detection problem in SQL. We first aggregate deposits by account and month, then identify runs of consecutive violating months.

Some important edge cases include:

  • Accounts with only one violating month, these are not suspicious.
  • Accounts where violating months are separated by a non-violating month.
  • Months with no creditor transactions at all.
  • Accounts where the monthly income equals max_income.
  • Multiple creditor transactions within the same month, which must be summed together.

Since the input is relational data, the intended solution relies heavily on SQL aggregation, joins, and date manipulation.

Approaches

Brute Force Approach

A brute force solution would process every account independently and examine all of its transactions month by month.

The approach would work like this:

  1. Filter only 'Creditor' transactions.
  2. Group transactions by (account_id, year-month).
  3. Compute the total income for every month.
  4. Compare the monthly income against max_income.
  5. Sort the months chronologically for each account.
  6. Check every adjacent pair of months to determine whether:
  • both exceed the limit,
  • and the months are consecutive.

This approach is correct because it explicitly computes every monthly income and directly checks the suspicious condition.

However, it can become inefficient if implemented naively outside SQL because:

  • each account may require repeated scans,
  • chronological comparisons require sorting,
  • and manually checking consecutive months introduces additional overhead.

In large datasets, repeatedly traversing transaction records account by account becomes expensive.

Optimal Approach

The key observation is that this problem naturally decomposes into two SQL operations:

  1. Aggregate monthly income.
  2. Detect consecutive violating months.

Instead of processing transactions repeatedly, we first create a compact monthly summary table. Each row in this summary represents:

(account_id, month, total_income)

After that, we only need to identify whether two neighboring months for the same account are consecutive and both exceed the threshold.

SQL window functions or self joins make this efficient because they allow us to compare each month directly with its neighboring month without repeatedly scanning the entire dataset.

The optimal solution therefore:

  • aggregates once,
  • filters once,
  • and performs efficient chronological comparisons.
Approach Time Complexity Space Complexity Notes
Brute Force O(T log T) O(T) Aggregate and repeatedly sort/check months manually
Optimal O(T log T) O(T) Aggregate monthly income once, then use SQL joins/window logic

Here, T represents the number of transactions.

Algorithm Walkthrough

Step 1: Filter Creditor Transactions

We first ignore all 'Debtor' transactions because withdrawals do not contribute to income.

Only rows with:

type = 'Creditor'

are relevant.

This reduces unnecessary processing and focuses only on deposit activity.

Step 2: Aggregate Income by Account and Month

For every account and every month, we compute:

SUM(amount)

We group by:

  • account_id
  • year-month extracted from day

This creates a monthly income summary.

For example:

account_id month income
3 2021-06 300100
3 2021-07 64900

This transformation is important because the suspicious condition applies at the monthly level, not transaction level.

Step 3: Join with Accounts Table

Next, we compare each monthly income against the corresponding max_income.

We join the aggregated monthly table with Accounts using:

account_id

Then we keep only rows where:

income > max_income

These are the violating months.

Step 4: Detect Consecutive Months

Now we must determine whether an account has two consecutive violating months.

For every violating month, we compare it against another violating month from the same account where:

month_difference = 1

This can be done using:

  • a self join,
  • or window functions such as LAG.

The self join solution checks whether:

TIMESTAMPDIFF(MONTH, prev_month, current_month) = 1

If true, the account is suspicious.

Step 5: Return Distinct Account IDs

An account may contain multiple consecutive violating month pairs.

We return distinct account_id values only once.

Why it works

The algorithm works because it directly models the definition of suspicious activity.

The aggregation step guarantees that every monthly income is computed correctly. The filtering step guarantees that only months exceeding the threshold are considered. Finally, the consecutive month comparison guarantees that only accounts with adjacent violating months are returned.

Since every suspicious account must contain at least one pair of consecutive violating months, and every such pair is explicitly checked, the algorithm is correct.

Python Solution

Although this is a database problem, the equivalent logic in Python helps clarify the algorithmic thinking.

from collections import defaultdict
from typing import List

class Solution:
    def suspiciousBankAccounts(
        self,
        accounts: List[List[int]],
        transactions: List[List]
    ) -> List[int]:

        max_income = {}
        for account_id, income_limit in accounts:
            max_income[account_id] = income_limit

        monthly_income = defaultdict(int)

        for transaction_id, account_id, trans_type, amount, day in transactions:
            if trans_type != "Creditor":
                continue

            month_key = day[:7]
            monthly_income[(account_id, month_key)] += amount

        violating_months = defaultdict(list)

        for (account_id, month), income in monthly_income.items():
            if income > max_income[account_id]:
                violating_months[account_id].append(month)

        suspicious_accounts = []

        for account_id, months in violating_months.items():
            months.sort()

            for i in range(1, len(months)):
                prev_year, prev_month = map(int, months[i - 1].split("-"))
                curr_year, curr_month = map(int, months[i].split("-"))

                prev_total = prev_year * 12 + prev_month
                curr_total = curr_year * 12 + curr_month

                if curr_total - prev_total == 1:
                    suspicious_accounts.append(account_id)
                    break

        return suspicious_accounts

The implementation begins by storing the maximum income limit for every account in a dictionary for constant time lookups.

Next, we aggregate all creditor transactions by (account_id, month). The month is extracted using the first seven characters of the date string, producing a YYYY-MM representation.

After computing monthly totals, we keep only the months where the income exceeds the allowed maximum.

For each account, the violating months are sorted chronologically. We then convert each month into a numeric representation:

year * 12 + month

This makes consecutive month detection straightforward because consecutive calendar months differ by exactly 1.

As soon as one consecutive pair is found, the account is marked suspicious.

Go Solution

package main

import (
	"sort"
	"strconv"
	"strings"
)

type Transaction struct {
	TransactionID int
	AccountID     int
	Type          string
	Amount        int
	Day           string
}

type Solution struct{}

func (s Solution) SuspiciousBankAccounts(
	accounts [][]int,
	transactions []Transaction,
) []int {

	maxIncome := make(map[int]int)

	for _, acc := range accounts {
		maxIncome[acc[0]] = acc[1]
	}

	monthlyIncome := make(map[[2]string]int)

	for _, t := range transactions {
		if t.Type != "Creditor" {
			continue
		}

		monthKey := t.Day[:7]

		key := [2]string{
			strconv.Itoa(t.AccountID),
			monthKey,
		}

		monthlyIncome[key] += t.Amount
	}

	violatingMonths := make(map[int][]string)

	for key, income := range monthlyIncome {
		accountID, _ := strconv.Atoi(key[0])
		month := key[1]

		if income > maxIncome[accountID] {
			violatingMonths[accountID] =
				append(violatingMonths[accountID], month)
		}
	}

	result := []int{}

	for accountID, months := range violatingMonths {
		sort.Strings(months)

		for i := 1; i < len(months); i++ {
			prev := convertMonth(months[i-1])
			curr := convertMonth(months[i])

			if curr-prev == 1 {
				result = append(result, accountID)
				break
			}
		}
	}

	return result
}

func convertMonth(month string) int {
	parts := strings.Split(month, "-")

	year, _ := strconv.Atoi(parts[0])
	mon, _ := strconv.Atoi(parts[1])

	return year*12 + mon
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is that Go requires explicit type definitions and manual string parsing. We use maps extensively:

  • map[int]int for income limits,
  • map[[2]string]int for monthly aggregation,
  • map[int][]string for violating months.

Go slices are used instead of Python lists, and sort.Strings handles chronological ordering because the YYYY-MM format is lexicographically sortable.

Unlike Python, Go does not have tuple dictionary keys directly, so a fixed-size string array is used as the composite map key.

Worked Examples

Example 1

Input:

Accounts:

account_id max_income
3 21000
4 10400

Transactions:

transaction_id account_id type amount day
2 3 Creditor 107100 2021-06-02
10 3 Creditor 102100 2021-06-15
7 3 Creditor 90900 2021-06-14
8 3 Creditor 64900 2021-07-26
1 4 Creditor 49300 2021-05-03
4 4 Creditor 10400 2021-06-20
14 4 Creditor 56300 2021-07-21

Step 1: Aggregate Monthly Income

account_id month total_income
3 2021-06 300100
3 2021-07 64900
4 2021-05 49300
4 2021-06 10400
4 2021-07 56300

Step 2: Compare Against max_income

For account 3:

month income exceeds?
2021-06 300100 Yes
2021-07 64900 Yes

For account 4:

month income exceeds?
2021-05 49300 Yes
2021-06 10400 No
2021-07 56300 Yes

Step 3: Check Consecutive Months

Account 3:

2021-06 -> 2021-07
difference = 1 month

Suspicious.

Account 4:

2021-05 -> 2021-07
difference = 2 months

Not suspicious.

Final result:

account_id
3

Complexity Analysis

Measure Complexity Explanation
Time O(T log T) Aggregation is linear, sorting violating months dominates
Space O(T) Monthly aggregation structures store transaction summaries

The algorithm processes every transaction once while building monthly income totals.

After aggregation, each account's violating months are sorted. In the worst case, all transactions belong to unique months, causing sorting overhead. Therefore, the overall complexity becomes O(T log T).

The auxiliary space usage comes from storing monthly aggregates and violating month lists.

Test Cases

from collections import defaultdict

class Solution:
    def suspiciousBankAccounts(self, accounts, transactions):
        max_income = {}

        for account_id, limit in accounts:
            max_income[account_id] = limit

        monthly_income = defaultdict(int)

        for _, account_id, trans_type, amount, day in transactions:
            if trans_type != "Creditor":
                continue

            month = day[:7]
            monthly_income[(account_id, month)] += amount

        violating = defaultdict(list)

        for (account_id, month), income in monthly_income.items():
            if income > max_income[account_id]:
                violating[account_id].append(month)

        result = []

        for account_id, months in violating.items():
            months.sort()

            for i in range(1, len(months)):
                py, pm = map(int, months[i - 1].split("-"))
                cy, cm = map(int, months[i].split("-"))

                prev = py * 12 + pm
                curr = cy * 12 + cm

                if curr - prev == 1:
                    result.append(account_id)
                    break

        return sorted(result)

solver = Solution()

# provided example
assert solver.suspiciousBankAccounts(
    [[3, 21000], [4, 10400]],
    [
        [2, 3, "Creditor", 107100, "2021-06-02"],
        [10, 3, "Creditor", 102100, "2021-06-15"],
        [7, 3, "Creditor", 90900, "2021-06-14"],
        [8, 3, "Creditor", 64900, "2021-07-26"],
        [1, 4, "Creditor", 49300, "2021-05-03"],
        [4, 4, "Creditor", 10400, "2021-06-20"],
        [14, 4, "Creditor", 56300, "2021-07-21"],
    ]
) == [3]  # basic example

# exactly equal to max income does not count
assert solver.suspiciousBankAccounts(
    [[1, 100]],
    [
        [1, 1, "Creditor", 100, "2021-01-01"],
        [2, 1, "Creditor", 100, "2021-02-01"],
    ]
) == []  # equality should not qualify

# consecutive violating months
assert solver.suspiciousBankAccounts(
    [[1, 100]],
    [
        [1, 1, "Creditor", 200, "2021-01-01"],
        [2, 1, "Creditor", 300, "2021-02-01"],
    ]
) == [1]  # two consecutive violating months

# non-consecutive violating months
assert solver.suspiciousBankAccounts(
    [[1, 100]],
    [
        [1, 1, "Creditor", 200, "2021-01-01"],
        [2, 1, "Creditor", 300, "2021-03-01"],
    ]
) == []  # missing February breaks consecutiveness

# debtor transactions ignored
assert solver.suspiciousBankAccounts(
    [[1, 100]],
    [
        [1, 1, "Debtor", 1000, "2021-01-01"],
        [2, 1, "Creditor", 200, "2021-02-01"],
        [3, 1, "Creditor", 300, "2021-03-01"],
    ]
) == [1]  # debtor should not affect income

# multiple creditor transactions same month
assert solver.suspiciousBankAccounts(
    [[1, 500]],
    [
        [1, 1, "Creditor", 300, "2021-01-01"],
        [2, 1, "Creditor", 400, "2021-01-15"],
        [3, 1, "Creditor", 700, "2021-02-01"],
    ]
) == [1]  # monthly aggregation required

# year transition consecutive
assert solver.suspiciousBankAccounts(
    [[1, 100]],
    [
        [1, 1, "Creditor", 200, "2021-12-01"],
        [2, 1, "Creditor", 300, "2022-01-01"],
    ]
) == [1]  # December to January is consecutive
Test Why
Provided example Validates the main problem scenario
Equal to max income Ensures strict greater-than comparison
Consecutive violating months Confirms suspicious detection
Non-consecutive months Verifies month-gap handling
Debtor transactions Ensures withdrawals are ignored
Multiple same-month deposits Confirms monthly aggregation
Year transition Validates consecutive logic across years

Edge Cases

Monthly Income Equals max_income

One subtle edge case occurs when the monthly income exactly matches the allowed maximum.

The problem requires the income to exceed the threshold, not merely reach it. A careless implementation using:

>=

instead of:

>

would incorrectly mark accounts as suspicious.

The implementation explicitly checks:

income > max_income[account_id]

which correctly handles this case.

Missing Months Between Violations

Another important edge case occurs when an account exceeds the threshold in two months that are not consecutive.

For example:

January -> exceeds
February -> does not exceed
March -> exceeds

A naive implementation that simply counts violating months would incorrectly mark this account suspicious.

The solution avoids this bug by converting months into numeric representations and ensuring the difference equals exactly 1.

Multiple Transactions in the Same Month

An account may contain many deposit transactions within a single month.

A naive implementation might compare each transaction individually against max_income, which is incorrect because the condition applies to the total monthly income.

The aggregation step correctly sums all creditor transactions before performing the comparison. This guarantees accurate monthly totals regardless of how many transactions occur within the month.