Domain 2MediumMEDIUM

Active Businesses

Identify teams with at least two distinct activity types within their valid time windows using hash maps for aggregation and sets to handle uniqueness.

Domain: medium•Updated: 2026-09-09
#hash_map#set#O(N)#sorting

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 O(N2)O(N^2) 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 (≥2\ge 2). Finally, sort the result list for deterministic output order as required by many LeetCode problems involving ID lists.

Approach

  1. Data Structure: Initialize a dictionary (defaultdict(set)) where each key is a team_id and the value stores unique activity types encountered so far. This automatically handles duplicate records within the same team/type combination without manual counting logic.
  2. Aggregation Loop: Iterate through every record in the input list:
    • Extract team_id. If null or invalid, skip (robustness).
    • Add activity_type to the set associated with that team_id. This ensures uniqueness per team regardless of how many times an activity occurred.
  3. 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_id into a results list.
  4. Output Formatting: Sort the collected team IDs numerically before returning them to satisfy standard output requirements for ID-based problems.

Complexity Analysis

  • Time Complexity: O(N+Klog⁡K)O(N + K \log K), where NN is the number of activity records and KK is the number of unique teams found in the input. We iterate through all records once (O(N)O(N)) to build sets (amortized O(1)O(1) per insertion). Finally, we sort the result list which takes O(Klog⁡K)O(K \log K). 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: O(N)O(N) or more precisely O(T+A)O(T + A) where TT is unique team IDs and AA 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 set for 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).