Find Users with Persistent Behavior Patterns solution and explanation
2 more videos on this problem
Leetcode HARD 3832 - Window Functions in SQL - Users with Persistent Behavior Patterns | EDSEveryday Data Science · 10:27 · 835 views
LeetCode, SQL, 3832. Find Users with Persistent Behavior Patterns, HARDДиванная аналитика · 49:04 · 19 views
LeetCode SQL Problem - Find Users with Persistent Behavior Patterns #leetcode #sqlRanvir Singh Matharu · 0:14 · 13 views
The problem
Table: activity
+--------------+---------+ | Column Name | Type | +--------------+---------+ | user_id | int | | action_date | date | | action | varchar | +--------------+---------+ (user_id, action_date, action) is the primary key (unique value) for this table. Each row represents a user performing a specific action on a given date.
Write a solution to identify behaviorally stable users based on the following definition:
- A user is considered behaviorally stable if there exists a sequence of at least
5consecutive days such that:- The user performed exactly one action per day during that period.
- The action is the same on all those consecutive days.
- If a user has multiple qualifying sequences, only consider the sequence with the maximum length.
Return the result table ordered by streak_length in descending order, then by user_id in ascending order.
The result format is in the following example.
Example:
Input:
activity table:
+---------+-------------+--------+ | user_id | action_date | action | +---------+-------------+--------+ | 1 | 2024-01-01 | login | | 1 | 2024-01-02 | login | | 1 | 2024-01-03 | login | | 1 | 2024-01-04 | login | | 1 | 2024-01-05 | login | | 1 | 2024-01-06 | logout | | 2 | 2024-01-01 | click | | 2 | 2024-01-02 | click | | 2 | 2024-01-03 | click | | 2 | 2024-01-04 | click | | 3 | 2024-01-01 | view | | 3 | 2024-01-02 | view | | 3 | 2024-01-03 | view | | 3 | 2024-01-04 | view | | 3 | 2024-01-05 | view | | 3 | 2024-01-06 | view | | 3 | 2024-01-07 | view | +---------+-------------+--------+
Output:
+---------+--------+---------------+------------+------------+ | user_id | action | streak_length | start_date | end_date | +---------+--------+---------------+------------+------------+ | 3 | view | 7 | 2024-01-01 | 2024-01-07 | | 1 | login | 5 | 2024-01-01 | 2024-01-05 | +---------+--------+---------------+------------+------------+
Explanation:
- User 1:
- Performed
loginfrom 2024-01-01 to 2024-01-05 on consecutive days - Each day has exactly one action, and the action is the same
- Streak length = 5 (meets minimum requirement)
- The action changes on 2024-01-06, ending the streak
- Performed
- User 2:
- Performed
clickfor only 4 consecutive days - Does not meet the minimum streak length of 5
- Excluded from the result
- Performed
- User 3:
- Performed
viewfor 7 consecutive days - This is the longest valid sequence for this user
- Included in the result
- Performed
The Results table is ordered by streak_length in descending order, then by user_id in ascending order
Approach overview
Problem Overview: You have a table of per-user activity records. Find the users whose behavior persists, meaning a qualifying condition holds across consecutive periods rather than in isolated rows. The core difficulty is detecting unbroken runs per user, not just counting matches.
Approach 1: Brute Force Self-Join (O(n^2) time, O(1) extra space)
For every row, scan the table again to check whether the same user has matching rows in each following period. You repeat the check for every candidate streak length. This works on small inputs and proves you understand the definition of persistence. It fails on large tables because each user's history is re-read many times, and the self-join grows quadratically with row count.
Approach 2: Sort, Then Scan Per User (O(n log n) time, O(n) space)
Filter rows that satisfy the base condition, sort by user and period, then walk each user's rows once. Keep a running streak counter that resets when the period gap is larger than one or the condition breaks. Mark the user as persistent once the counter reaches the threshold. The sort dominates the runtime, and the scan itself is linear. This is a solid answer when you are working in a language without SQL window functions.
Approach 3: Gaps-and-Islands with Grouping and Aggregation (O(n log n) time in general, O(n) space)
This is the approach to use in SQL or Pandas. First filter to the qualifying rows. Then compute a group key that stays constant within each consecutive run. A common trick is to subtract a row number from the period value, so consecutive periods produce the same key. Group by user and that key, aggregate with COUNT or MAX - MIN on the period, and keep users whose largest run meets the threshold. The filter reduces the input before any grouping, and the aggregation returns one row per run instead of one per record. Each step is a single pass over grouped data, so the query stays readable and avoids nested loops.
Recommended for interviews: Start with the brute force to show you understand what persistence means. Then move to the grouping and aggregation approach and explain why the run key works. The brute force shows understanding, but the optimal approach shows skill. Interviewers want to see you reduce the problem to a grouping step rather than comparing rows pairwise. If the problem is in SQL, expect follow-ups about how the run key is computed and what happens when a user has multiple qualifying runs.
Practice related patterns in SQL, database, and sliding window problems to get comfortable with consecutive-run logic.
Solution
Thinking
A stable user has at least five consecutive days with exactly one action, always the same. Several streaks may exist; only the longest is kept.
Days with more than one action must be dropped, or consecutiveness is ill-defined.
After sorting each
(user_id,action)by date, date minus row number groups contiguous days into onegrp.Aggregate lengths, keep those
\ge 5, rank one streak per user, and sort by length then id.
We first need to filter user dates with only a single action per day, then identify consecutive intervals among these dates, and finally aggregate these intervals to calculate the streak length and filter records that meet the criteria.
# Write your MySQL query statement below
WITH
daily_counts AS (
-- Step 1: Filter user dates with exactly one record per day (meeting the requirement of "exactly one action per day")
SELECT
user_id,
action_date,
action,
COUNT(*) OVER (PARTITION BY user_id, action_date) AS cnt
FROM activity
),
filtered_activity AS (
-- Step 2: Filter out data with multiple actions on the same day
SELECT user_id, action_date, action
FROM daily_counts
WHERE cnt = 1
),
streak_groups AS (
-- Step 3: Group consecutive dates using the method of subtracting row number from date
SELECT
user_id,
action,
action_date,
DATE_SUB(
action_date,
INTERVAL ROW_NUMBER() OVER (
PARTITION BY user_id, action
ORDER BY action_date
) DAY
) AS grp
FROM filtered_activity
),
streak_summary AS (
-- Step 4: Calculate the length of each consecutive segment and only keep records with length >= 5
SELECT
user_id,
action,
COUNT(*) AS streak_length,
MIN(action_date) AS start_date,
MAX(action_date) AS end_date,
-- Sort different streaks for each user to facilitate getting the maximum value later
ROW_NUMBER() OVER (
PARTITION BY user_id
ORDER BY COUNT(*) DESC
) AS rnk
FROM streak_groups
GROUP BY user_id, action, grp
HAVING streak_length >= 5
)
-- Step 5: Extract the longest record for each qualified user and sort
SELECT user_id, action, streak_length, start_date, end_date
FROM streak_summary
WHERE rnk = 1
ORDER BY streak_length DESC, user_id ASC;import pandas as pd
def find_behaviorally_stable_users(activity: pd.DataFrame) -> pd.DataFrame:
activity['action_date'] = pd.to_datetime(activity['action_date'])
# Filter users with only a single action per day
df = activity.assign(cnt=activity.groupby(['user_id', 'action_date'])['action'].transform('count'))
df = df[df['cnt'] == 1].sort_values(['user_id', 'action', 'action_date'])
# Identify consecutive intervals
df['rn'] = df.groupby(['user_id', 'action'])['action_date'].rank(method='first')
df['grp'] = df['action_date'] - pd.to_timedelta(df['rn'], unit='D')
# Aggregate streaks
streaks = df.groupby(['user_id', 'action', 'grp']).agg(
streak_length=('action_date', 'count'),
start_date=('action_date', 'min'),
end_date=('action_date', 'max')
).reset_index()
# Filter and get the longest streak for each user
res = streaks[streaks['streak_length'] >= 5].sort_values(
['streak_length', 'user_id'], ascending=[False, True]
)
return res.groupby('user_id').head(1)[['user_id', 'action', 'streak_length', 'start_date', 'end_date']]Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Self-Join | O(n^2) | O(1) | Tiny inputs or first pass to clarify the definition |
| Sort and Scan Per User | O(n log n) | O(n) | Procedural code without SQL window functions |
| Gaps-and-Islands with Grouping and Aggregation | O(n log n) | O(n) | General case in SQL or Pandas, recommended |
Frequently asked questions
Is Find Users with Persistent Behavior Patterns easy or hard?
It is rated Hard on FleetCode with a 47.6 percent acceptance rate. The difficulty comes from recognizing that persistence is a consecutive-run problem, not a simple count. Once you see the run key pattern, the implementation is short.
How to solve Find Users with Persistent Behavior Patterns in O(n)?
Use a single pass over rows already sorted by user and period. Keep a running streak counter per user that resets when the condition breaks or the period gap exceeds one. If the table is not sorted, the sort step adds O(n log n), so O(n) requires sorted input or a hash-based grouping pass.
Find Users with Persistent Behavior Patterns Python or Java solution?
In Python, use Pandas: filter with a boolean mask, sort by user and period, compute a run key with cumulative counts, then groupby and aggregate. In Java, sort records by user and period, then iterate once with a streak counter that resets on a break. Both run in O(n log n) time.
What is the best approach for Find Users with Persistent Behavior Patterns?
The best approach is gaps-and-islands with grouping and aggregation. Filter the qualifying rows first, compute a run key that stays constant across consecutive periods, then group by user and run key. This runs in O(n log n) time with O(n) space.
What data structure is used in Find Users with Persistent Behavior Patterns?
The problem is usually solved with a relational table and grouping operations rather than a classic data structure. In Pandas, you use a DataFrame with groupby and aggregation. In SQL, you use window functions such as ROW_NUMBER to build the run key, then GROUP BY on user and that key.
What is the time complexity of Find Users with Persistent Behavior Patterns?
The optimal solution runs in O(n log n) time, where n is the number of activity rows, because the grouping or sorting step dominates. A brute force self-join runs in O(n^2) time. Both approaches use O(n) extra space in the optimal case.
Is Find Users with Persistent Behavior Patterns asked at Google, Amazon, or Meta?
FleetCode does not tag this problem to a specific company. Consecutive-run and gaps-and-islands questions are common in SQL and data engineering interviews at large tech companies, so the underlying pattern is worth knowing even if this exact problem does not appear.
