Problem

Table: Accounts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

+----------------+------+
| Column Name    | Type |
+----------------+------+
| account_id     | int  |
| max_income     | int  |
+----------------+------+
account_id is the column with unique values for this table.
Each row contains information about the maximum monthly income for one bank account.

Table: `Transactions`

+----------------+----------+
| Column Name    | Type     |
+----------------+----------+
| transaction_id | int      |
| account_id     | int      |
| type           | ENUM     |
| amount         | int      |
| day            | datetime |
+----------------+----------+
transaction_id is the column with unique values for this table.
Each row contains information about one transaction.
type is ENUM (category) type of ('Creditor','Debtor') where 'Creditor' means the user deposited money into their account and 'Debtor' means the user withdrew money from their account.
amount is the amount of money deposited/withdrawn during the transaction.

A bank account is suspicious if the total income exceeds the max_income for this account for two or more consecutive months. The total income of an account in some month is the sum of all its deposits in that month (i.e., transactions of the type 'Creditor').

Write a solution to report the IDs of all suspicious bank accounts.

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
32
33
34
35
36
37
38
39

Input: 
Accounts table:
+------------+------------+
| account_id | max_income |
+------------+------------+
| 3          | 21000      |
| 4          | 10400      |
+------------+------------+
Transactions table:
+----------------+------------+----------+--------+---------------------+
| transaction_id | account_id | type     | amount | day                 |
+----------------+------------+----------+--------+---------------------+
| 2              | 3          | Creditor | 107100 | 2021-06-02 11:38:14 |
| 4              | 4          | Creditor | 10400  | 2021-06-20 12:39:18 |
| 11             | 4          | Debtor   | 58800  | 2021-07-23 12:41:55 |
| 1              | 4          | Creditor | 49300  | 2021-05-03 16:11:04 |
| 15             | 3          | Debtor   | 75500  | 2021-05-23 14:40:20 |
| 10             | 3          | Creditor | 102100 | 2021-06-15 10:37:16 |
| 14             | 4          | Creditor | 56300  | 2021-07-21 12:12:25 |
| 19             | 4          | Debtor   | 101100 | 2021-05-09 15:21:49 |
| 8              | 3          | Creditor | 64900  | 2021-07-26 15:09:56 |
| 7              | 3          | Creditor | 90900  | 2021-06-14 11:23:07 |
+----------------+------------+----------+--------+---------------------+
Output: 
+------------+
| account_id |
+------------+
| 3          |
+------------+
Explanation: 
For account 3:
- In 6-2021, the user had an income of 107100 + 102100 + 90900 = 300100.
- In 7-2021, the user had an income of 64900.
We can see that the income exceeded the max income of 21000 for two consecutive months, so we include 3 in the result table.
For account 4:
- In 5-2021, the user had an income of 49300.
- In 6-2021, the user had an income of 10400.
- In 7-2021, the user had an income of 56300.
We can see that the income exceeded the max income in May and July, but not in June. Since the account did not exceed the max income for two consecutive months, we do not include it in the result table.

Solution

Method 1 - Monthly Income Consecutive Check

Intuition

We aggregate monthly income for each account, flag months where income exceeds max_income, and then look for two consecutive flagged months for each account. If found, the account is suspicious.

Approach

First, for each account and month, sum the total ‘Creditor’ income. Then, for each account, check if there are two or more consecutive months where the income exceeds the max_income. We use window functions or self-joins to detect consecutive months.

Complexity

  • ⏰ Time complexity: O(N log N) – Aggregation groups transactions by account and month and the joins/window operations dominate; sorting/grouping cost is the main factor.
  • 🧺 Space complexity: O(M) – We may store intermediate monthly aggregates (one row per account/month) and temporary result sets.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

WITH monthly_income AS (
  SELECT t.account_id, YEAR(t.day) AS y, MONTH(t.day) AS m, SUM(t.amount) AS income
  FROM Transactions t
  WHERE t.type = 'Creditor'
  GROUP BY t.account_id, YEAR(t.day), MONTH(t.day)
),
flagged AS (
  SELECT mi.account_id, mi.y, mi.m, a.max_income,
         CASE WHEN mi.income > a.max_income THEN 1 ELSE 0 END AS over
  FROM monthly_income mi
  JOIN Accounts a ON mi.account_id = a.account_id
),
consec AS (
  SELECT f1.account_id
  FROM flagged f1
  JOIN flagged f2
    ON f1.account_id = f2.account_id
   AND ((f1.y = f2.y AND f1.m = f2.m - 1) OR (f1.y = f2.y - 1 AND f1.m = 12 AND f2.m = 1))
  WHERE f1.over = 1 AND f2.over = 1
)
SELECT DISTINCT account_id FROM consec;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

WITH monthly_income AS (
  SELECT t.account_id, EXTRACT(YEAR FROM t.day) AS y, EXTRACT(MONTH FROM t.day) AS m, SUM(t.amount) AS income
  FROM Transactions t
  WHERE t.type = 'Creditor'
  GROUP BY t.account_id, EXTRACT(YEAR FROM t.day), EXTRACT(MONTH FROM t.day)
),
flagged AS (
  SELECT mi.account_id, mi.y, mi.m, a.max_income,
         CASE WHEN mi.income > a.max_income THEN 1 ELSE 0 END AS over
  FROM monthly_income mi
  JOIN Accounts a ON mi.account_id = a.account_id
),
consec AS (
  SELECT f1.account_id
  FROM flagged f1
  JOIN flagged f2
    ON f1.account_id = f2.account_id
   AND ((f1.y = f2.y AND f1.m = f2.m - 1) OR (f1.y = f2.y - 1 AND f1.m = 12 AND f2.m = 1))
  WHERE f1.over = 1 AND f2.over = 1
)
SELECT DISTINCT account_id FROM consec;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

WITH monthly_income AS (
  SELECT t.account_id, EXTRACT(YEAR FROM t.day) AS y, EXTRACT(MONTH FROM t.day) AS m, SUM(t.amount) AS income
  FROM Transactions t
  WHERE t.type = 'Creditor'
  GROUP BY t.account_id, EXTRACT(YEAR FROM t.day), EXTRACT(MONTH FROM t.day)
),
flagged AS (
  SELECT mi.account_id, mi.y, mi.m, a.max_income,
         CASE WHEN mi.income > a.max_income THEN 1 ELSE 0 END AS over
  FROM monthly_income mi
  JOIN Accounts a ON mi.account_id = a.account_id
),
consec AS (
  SELECT f1.account_id
  FROM flagged f1
  JOIN flagged f2
    ON f1.account_id = f2.account_id
   AND ((f1.y = f2.y AND f1.m = f2.m - 1) OR (f1.y = f2.y - 1 AND f1.m = 12 AND f2.m = 1))
  WHERE f1.over = 1 AND f2.over = 1
)
SELECT DISTINCT account_id FROM consec;