LeetCode 1747 - Leetflex Banned Accounts

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to identify suspicious accounts in the LogInfo table. Each row represents a login session for a user account, including the account ID, the IP address used during the session, and the login and logout timestamps.

An account should be banned if there exists at least one moment in time where the same account is simultaneously active from two different IP addresses.

The important detail is that the sessions must overlap in time. Merely logging in from different IPs at different times is completely valid. We only ban an account if two sessions from different IP addresses intersect at any instant.

The input table contains:

Column	Meaning
`account_id`	The user account
`ip_address`	IP used during the session
`login`	Session start time
`logout`	Session end time

The problem guarantees that logout > login, so every session has positive duration.

The expected output is a table containing only the account_id values that should be banned.

A subtle but extremely important detail is how interval overlap is defined. The example with account 4 demonstrates that intervals are inclusive at both ends. One session ends at exactly 17:00:00, and another starts at exactly 17:00:00, and this still counts as overlapping.

That means two sessions overlap if:

session1.login <= session2.logout
AND
session2.login <= session1.logout

Several edge cases can easily cause bugs:

Two sessions touching exactly at a boundary still overlap.
Duplicate rows may exist.
Sessions from the same IP should not trigger a ban.
Multiple overlapping sessions may exist for the same account.
Sessions may be completely nested inside another session.

The core challenge is detecting whether an account has two overlapping intervals with different IP addresses.

Approaches

Brute Force Approach

The brute force solution compares every pair of sessions in the table.

For every pair of rows:

Check whether they belong to the same account.
Check whether the IP addresses are different.
Check whether the time intervals overlap.

If all three conditions are true, then that account should be included in the answer.

The overlap condition is:

login1 <= logout2
AND
login2 <= logout1

This works because two intervals overlap if each interval starts before the other one ends.

The brute force method is correct because it explicitly checks every possible pair of sessions. If any overlapping pair with different IPs exists, we will find it.

However, this approach is inefficient because comparing every pair requires quadratic time.

Optimal Approach

The optimal SQL solution uses a self join.

Instead of manually iterating through every pair in application code, we let the database engine efficiently join the table with itself.

The key insight is that the problem is fundamentally a pairwise interval overlap detection problem.

For two rows a and b, we need:

Same account
Different IP addresses
Overlapping intervals

A self join naturally models this relationship.

We also use DISTINCT because multiple overlapping pairs may exist for the same account.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every pair of sessions manually
Optimal	O(n²) worst case	O(1) extra	Self join with overlap filtering

Even though the SQL self join can still be quadratic in the worst case, it is the intended relational database solution and is typically optimized internally by the database engine.

Algorithm Walkthrough

Create two aliases of the LogInfo table, usually called a and b.

This allows us to compare one session against another session in the same table. 2. Match rows belonging to the same account.

We only care about concurrent activity for the same user, so we require:

a.account_id = b.account_id

Ensure the IP addresses are different.

Multiple overlapping sessions from the same IP are not suspicious.

a.ip_address != b.ip_address

Check whether the time intervals overlap.

Two intervals overlap if:

a.login <= b.logout
AND
b.login <= a.logout

This correctly handles:

Partial overlaps
Complete containment
Exact boundary touching

Select distinct account IDs.

An account may have many overlapping session pairs, but it should appear only once in the output.

Why it works

The algorithm checks every relevant pair of sessions belonging to the same account. The overlap condition mathematically guarantees that the two intervals share at least one instant in time. Since we additionally require different IP addresses, every returned account satisfies the exact definition of a banned account.

Conversely, if an account should be banned, then there exists at least one overlapping pair of sessions with different IPs, and the self join will find that pair.

Python Solution

Although this is a Database problem and normally solved with SQL, the following Python implementation demonstrates the same logic algorithmically.

from typing import List
from collections import defaultdict

class Solution:
    def bannedAccounts(self, log_info: List[List[int]]) -> List[int]:
        sessions_by_account = defaultdict(list)

        for account_id, ip_address, login, logout in log_info:
            sessions_by_account[account_id].append(
                (ip_address, login, logout)
            )

        banned_accounts = []

        for account_id, sessions in sessions_by_account.items():
            n = len(sessions)

            banned = False

            for i in range(n):
                ip1, login1, logout1 = sessions[i]

                for j in range(i + 1, n):
                    ip2, login2, logout2 = sessions[j]

                    if ip1 == ip2:
                        continue

                    overlaps = (
                        login1 <= logout2 and
                        login2 <= logout1
                    )

                    if overlaps:
                        banned_accounts.append(account_id)
                        banned = True
                        break

                if banned:
                    break

        return banned_accounts

The implementation first groups sessions by account ID using a hash map. This prevents unnecessary comparisons between different accounts.

For each account, we compare every pair of sessions. We skip pairs using the same IP address because they are not suspicious.

The overlap test directly implements the interval intersection condition:

login1 <= logout2 and login2 <= logout1

As soon as we find one suspicious overlap for an account, we add it to the result and stop checking additional pairs for that account.

This early termination slightly improves practical performance.

Go Solution

package main

type Session struct {
	ip     int
	login  int
	logout int
}

func bannedAccounts(logInfo [][]int) []int {
	sessionsByAccount := make(map[int][]Session)

	for _, row := range logInfo {
		accountID := row[0]
		ipAddress := row[1]
		login := row[2]
		logout := row[3]

		sessionsByAccount[accountID] = append(
			sessionsByAccount[accountID],
			Session{
				ip:     ipAddress,
				login:  login,
				logout: logout,
			},
		)
	}

	var result []int

	for accountID, sessions := range sessionsByAccount {
		n := len(sessions)

		banned := false

		for i := 0; i < n; i++ {
			for j := i + 1; j < n; j++ {
				s1 := sessions[i]
				s2 := sessions[j]

				if s1.ip == s2.ip {
					continue
				}

				overlaps := (
					s1.login <= s2.logout &&
					s2.login <= s1.logout
				)

				if overlaps {
					result = append(result, accountID)
					banned = true
					break
				}
			}

			if banned {
				break
			}
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version.

A small structural difference is the use of a dedicated Session struct to make the code more readable and type safe.

Go slices are dynamically resized automatically during append, so no manual memory management is needed.

There are no integer overflow concerns here because the problem constraints are small and timestamps are treated symbolically.

Worked Examples

Example 1

Input:

1 | 1  | 09:00 | 09:30
1 | 2  | 08:00 | 11:30
2 | 6  | 20:30 | 22:00
2 | 7  | 20:30 | 22:00 next day
3 | 9  | 16:00 | 16:59:59
3 | 13 | 17:00 | 17:59:59
4 | 10 | 16:00 | 17:00
4 | 11 | 17:00 | 17:59:59

Account 1

Sessions:

IP	Login	Logout
1	09:00	09:30
2	08:00	11:30

Check overlap:

Condition	Result
`09:00 <= 11:30`	True
`08:00 <= 09:30`	True

Both conditions are true, so the sessions overlap.

Since IPs are different, account 1 is banned.

Account 2

Sessions:

IP	Login	Logout
6	Day 1 20:30	Day 1 22:00
7	Day 2 20:30	Day 2 22:00

Check overlap:

Condition	Result
Day1 start <= Day2 end	True
Day2 start <= Day1 end	False

No overlap exists.

Account 2 is not banned.

Account 3

Sessions:

IP	Login	Logout
9	16:00	16:59:59
13	17:00	17:59:59

Check overlap:

Condition	Result
`16:00 <= 17:59:59`	True
`17:00 <= 16:59:59`	False

No overlap exists.

Account 3 is not banned.

Account 4

Sessions:

IP	Login	Logout
10	16:00	17:00
11	17:00	17:59:59

Check overlap:

Condition	Result
`16:00 <= 17:59:59`	True
`17:00 <= 17:00`	True

The intervals touch exactly at 17:00.

Because the comparison is inclusive, this counts as overlap.

Account 4 is banned.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every pair of sessions for an account may need comparison
Space	O(n)	Hash map stores grouped sessions

The dominant cost comes from pairwise comparisons within each account's session list. In the worst case, if all sessions belong to one account, we compare every pair.

The additional memory usage comes from grouping sessions by account ID.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def bannedAccounts(self, log_info: List[List[int]]) -> List[int]:
        sessions_by_account = defaultdict(list)

        for account_id, ip_address, login, logout in log_info:
            sessions_by_account[account_id].append(
                (ip_address, login, logout)
            )

        banned_accounts = []

        for account_id, sessions in sessions_by_account.items():
            n = len(sessions)

            banned = False

            for i in range(n):
                ip1, login1, logout1 = sessions[i]

                for j in range(i + 1, n):
                    ip2, login2, logout2 = sessions[j]

                    if ip1 == ip2:
                        continue

                    if (
                        login1 <= logout2 and
                        login2 <= logout1
                    ):
                        banned_accounts.append(account_id)
                        banned = True
                        break

                if banned:
                    break

        return sorted(banned_accounts)

solution = Solution()

# basic overlapping intervals with different IPs
assert solution.bannedAccounts([
    [1, 1, 9, 30],
    [1, 2, 8, 40]
]) == [1]

# different IPs but no overlap
assert solution.bannedAccounts([
    [1, 1, 1, 5],
    [1, 2, 6, 10]
]) == []

# touching exactly at boundary still overlaps
assert solution.bannedAccounts([
    [1, 1, 1, 5],
    [1, 2, 5, 10]
]) == [1]

# same IP overlapping should not ban
assert solution.bannedAccounts([
    [1, 1, 1, 10],
    [1, 1, 5, 15]
]) == []

# multiple accounts, only one suspicious
assert solution.bannedAccounts([
    [1, 1, 1, 10],
    [1, 2, 5, 15],
    [2, 3, 1, 5],
    [2, 4, 6, 10]
]) == [1]

# nested interval overlap
assert solution.bannedAccounts([
    [1, 1, 1, 20],
    [1, 2, 5, 10]
]) == [1]

# duplicate rows should not break logic
assert solution.bannedAccounts([
    [1, 1, 1, 10],
    [1, 1, 1, 10],
    [1, 2, 5, 15]
]) == [1]

# single session account cannot be banned
assert solution.bannedAccounts([
    [1, 1, 1, 10]
]) == []

# multiple overlapping pairs for same account
assert solution.bannedAccounts([
    [1, 1, 1, 10],
    [1, 2, 2, 9],
    [1, 3, 3, 8]
]) == [1]

# multiple valid banned accounts
assert solution.bannedAccounts([
    [1, 1, 1, 10],
    [1, 2, 5, 15],
    [2, 3, 1, 8],
    [2, 4, 2, 9]
]) == [1, 2]

Test Summary

Test	Why
Simple overlap	Verifies basic detection
Non-overlapping sessions	Ensures no false positives
Boundary touching	Confirms inclusive overlap logic
Same IP overlap	Ensures different IP requirement
Multiple accounts	Validates account isolation
Nested intervals	Tests full containment overlap
Duplicate rows	Ensures duplicates do not break logic
Single session	Minimum valid input
Many overlapping sessions	Ensures early detection still works
Multiple banned accounts	Verifies multi-account output

Edge Cases

Sessions Touching at Exactly One Timestamp

One of the trickiest cases is when one session ends at the exact moment another session begins.

For example:

Session A: 16:00 -> 17:00
Session B: 17:00 -> 18:00

A strict inequality check would incorrectly treat these as non-overlapping. The problem statement explicitly considers this an overlap. The implementation correctly handles this by using <= comparisons instead of <.

Multiple Sessions Using the Same IP

An account may legitimately have overlapping sessions from the same IP address. For example, a user could have multiple browser tabs open simultaneously.

A naive implementation that only checks interval overlap would incorrectly ban such users. The solution explicitly checks:

if ip1 == ip2:
    continue

This guarantees only different IP addresses trigger bans.

Duplicate Rows

The table may contain duplicate rows. A careless implementation might accidentally add the same account multiple times or perform redundant work.

The implementation handles this safely because:

Duplicate rows with the same IP do not trigger bans.
Once an account is marked banned, processing stops early.
The result contains each banned account only once.