Problem Breakdown
Goal: Identify unique team_ids classified as “active” based on the count of distinct activity_types.
Inputs: A list of activity records containing at least team_id, activity_type, and potentially temporal data (e.g., season/date).
Outputs: A sorted list of integers representing active team IDs.
Implicit Constraints & Edge Cases:
- Distinct Counting: We must count unique combinations, not total occurrences. Sets are ideal for this.
- Time Windows: The logic assumes records provided fall within the relevant “first month/season” window or that filtering is handled upstream; if raw dates were present without a season column, date arithmetic would be required (not shown here).
- Empty Input: If no teams meet criteria or input list is empty, return an empty sorted list.
- Null Safety: While LeetCode inputs are typically clean, robust code should handle missing keys gracefully to prevent runtime errors in production scenarios.
Intuition
Brute Force Approach: Iterate through every team and scan their activity history repeatedly for each season/window check. This leads to or worse complexity if not optimized with aggregation structures. Complexity: High due to repeated scans of data subsets.
Key Insight: The condition “active” relies on the count of unique activities per team, which is a classic candidate for Hash Map (Dictionary) + Set optimization. We can aggregate all distinct activity types encountered by each team in a single pass over the dataset.
Optimal Approach: Use a dictionary where keys are team_id and values are Sets containing unique activity_types. After populating this structure, iterate through it to filter teams meeting the count threshold (). Finally, sort the result list for deterministic output order as required by many LeetCode problems involving ID lists.
Approach
- Data Structure: Initialize a dictionary (
defaultdict(set)) where each key is ateam_idand the value stores unique activity types encountered so far. This automatically handles duplicate records within the same team/type combination without manual counting logic. - Aggregation Loop: Iterate through every record in the input list:
- Extract
team_id. If null or invalid, skip (robustness). - Add
activity_typeto the set associated with thatteam_id. This ensures uniqueness per team regardless of how many times an activity occurred.
- Extract
- Filtering: Iterate through the populated dictionary values:
- Check if the size of the unique activities set is greater than or equal to 2 (the “active” threshold).
- If true, collect the
team_idinto a results list.
- Output Formatting: Sort the collected team IDs numerically before returning them to satisfy standard output requirements for ID-based problems.
Complexity Analysis
- Time Complexity: , where is the number of activity records and is the number of unique teams found in the input. We iterate through all records once () to build sets (amortized per insertion). Finally, we sort the result list which takes . Since sorting dominates only if active teams are many relative to N, but generally dominated by reading input in large datasets, it is often simplified as linear with respect to input size for high-level analysis.
- Space Complexity: or more precisely where is unique team IDs and is total distinct activity types stored across all teams (bounded by the number of records). In worst case, every record has a unique type per team.
Solution
from collections import defaultdict
import math
def get_active_businesses(activities):
"""
Identifies active businesses based on having at least two different
activities within their valid time windows (or overall if pre-filtered).
Args:
activities: List of dicts with keys 'team_id', 'activity_type'.
Assumes records are relevant to the query window.
Returns:
Sorted list of active team_ids.
"""
# Dictionary to store unique activity types for each team
# Key: team_id, Value: Set of distinct activity_types encountered
team_activities = defaultdict(set)
for record in activities:
try:
team_id = record['team_id']
if not isinstance(team_id, int): # Basic validation against non-integer IDs
continue
activity_type = record.get('activity_type')
# Ensure we don't add None or empty strings as valid types unless specified
if activity_type is not None:
team_activities[team_id].add(activity_type)
except (KeyError, TypeError):
# Handle malformed records gracefully in production scenarios
continue
active_teams = []
# Filter teams that have at least two distinct activities
for team_id, unique_types in team_activities.items():
if len(unique_types) >= 2:
active_teams.append(team_id)
return sorted(active_teams)
Edge Cases Handled
- No Activities: Returns empty list immediately as the dictionary remains empty and loop over items yields nothing.
- Single Activity Type per Team: Teams with only one distinct activity type are excluded by
len(unique_types) >= 2. - Duplicate Records: Using a Python
setfor values ensures that identical(team_id, activity_type)combinations don’t inflate counts artificially; duplicates within the same window/record set are ignored. - Null/Invalid IDs: The code includes checks (
if not isinstance,.get()) to prevent crashes on missing keys or non-standard types, though LeetCode inputs usually guarantee valid primary keys. - Sorting Requirement: Explicitly sorts output at return time to ensure deterministic ordering regardless of hash map insertion order (Python 3.7+ preserves insertion order but LC often requires sorted ID lists).