Problem Description

You are given three arrays of equal length n that describe properties of n coupons:

• code[i]: a string representing the coupon's identifier
• businessLine[i]: a string denoting the coupon's business category
• isActive[i]: a boolean indicating if the coupon is currently active

A coupon is considered valid when it meets all three conditions:

1. Its code is non-empty and contains only alphanumeric characters (a-z, A-Z, 0-9) and underscores (_)
2. Its businessLine is exactly one of these four categories: "electronics", "grocery", "pharmacy", or "restaurant"
3. Its isActive status is true

Your task is to return an array containing the codes of all valid coupons. The output should be sorted using a two-level sorting criteria:

• Primary sort: By business line in this specific order: "electronics", "grocery", "pharmacy", "restaurant"
• Secondary sort: Within each business category, sort codes lexicographically (alphabetically in ascending order)

For example, if you have valid coupons with codes ["ABC", "XYZ"] in electronics and ["DEF"] in grocery, the output would be ["ABC", "XYZ", "DEF"] - first all electronics coupons (sorted alphabetically), then all grocery coupons (sorted alphabetically), and so on.

Intuition

The problem is essentially asking us to filter and sort data based on specific criteria. Let's think about how to approach this step by step.

First, we need to identify which coupons are valid. Since we have three conditions that must all be true, we need to check each coupon against all three criteria. The natural approach is to iterate through all coupons and keep track of which ones pass all the validation checks.

For the code validation, we need to ensure the string is non-empty and contains only allowed characters (alphanumeric and underscore). We can check each character individually to see if it meets these requirements.

For the business line validation, since we have exactly four valid categories, we can use a set to store these valid options and check membership efficiently. Using a set like {"electronics", "grocery", "pharmacy", "restaurant"} makes the validation a simple in operation.

The active status check is straightforward - just verify that isActive[i] is true.

Once we identify all valid coupons, we face a sorting challenge. We need to sort by two criteria: first by business line (in a specific order), then by code (lexicographically). The key insight here is that we can't use simple alphabetical sorting for business lines because the required order ("electronics", "grocery", "pharmacy", "restaurant") doesn't match alphabetical order.

To handle this custom sorting, we can store the indices of valid coupons first, then sort these indices using a custom key function. The key function would return a tuple (businessLine[i], code[i]) for each index i. Python's sorting naturally handles tuples by comparing the first element first, then the second element if the first elements are equal. Since the business lines are strings and happen to be in the correct order alphabetically, this approach works perfectly.

Finally, we use the sorted indices to extract the corresponding codes from the original code array and return them in the correct order.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a simulation approach where we directly check each condition and collect valid coupons. Here's how the solution works:

1. Helper Function for Code Validation

We define a helper function check(s) to validate coupon codes:

def check(s: str) -> bool:
    if not s:
        return False
    for c in s:
        if not (c.isalpha() or c.isdigit() or c == "_"):
            return False
    return True

This function returns False if the string is empty or contains any character that isn't alphanumeric or underscore.

2. Define Valid Business Categories

We create a set containing the four valid business categories:

bs = {"electronics", "grocery", "pharmacy", "restaurant"}

Using a set provides O(1) lookup time for membership checking.

3. Collect Valid Coupon Indices

We iterate through all coupons using enumerate and zip to process the three arrays simultaneously:

idx = []
for i, (c, b, a) in enumerate(zip(code, businessLine, isActive)):
    if a and b in bs and check(c):
        idx.append(i)

For each coupon at index i, we check:

• a (isActive) is True
• b (businessLine) is in our valid categories set
• c (code) passes our validation function

If all conditions are met, we store the index i in our idx list.

4. Custom Sorting

We sort the collected indices using a custom key function:

idx.sort(key=lambda i: (businessLine[i], code[i]))

The key function returns a tuple (businessLine[i], code[i]) for each index. Python sorts tuples lexicographically - first by the first element, then by the second if the first elements are equal.

Since the business categories happen to be in alphabetical order matching our required order ("electronics" < "grocery" < "pharmacy" < "restaurant"), this sorting naturally gives us the correct ordering.

5. Extract and Return Results

Finally, we use list comprehension to extract the codes of valid coupons in sorted order:

return [code[i] for i in idx]

Time Complexity: O(n·m + k·log(k)) where n is the number of coupons, m is the average length of coupon codes, and k is the number of valid coupons.

Space Complexity: O(k) for storing the indices of valid coupons.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works:

Input:

• code = ["SAVE20", "10OFF", "FREE@SHIP", "DEAL_5", ""]
• businessLine = ["electronics", "grocery", "electronics", "pharmacy", "grocery"]
• isActive = [True, True, True, True, False]

Step 1: Validate Each Coupon

Let's check each coupon (index 0 to 4):

Index 0: code="SAVE20", businessLine="electronics", isActive=True

• Code validation: "SAVE20" contains only letters and digits ✓
• Business line: "electronics" is in valid set ✓
• Active status: True ✓
• Valid - add index 0 to our list

Index 1: code="10OFF", businessLine="grocery", isActive=True

• Code validation: "10OFF" contains only digits and letters ✓
• Business line: "grocery" is in valid set ✓
• Active status: True ✓
• Valid - add index 1 to our list

Index 2: code="FREE@SHIP", businessLine="electronics", isActive=True

• Code validation: "FREE@SHIP" contains '@' which is not allowed ✗
• Invalid - skip this coupon

Index 3: code="DEAL_5", businessLine="pharmacy", isActive=True

• Code validation: "DEAL_5" contains letters, underscore, and digit ✓
• Business line: "pharmacy" is in valid set ✓
• Active status: True ✓
• Valid - add index 3 to our list

Index 4: code="", businessLine="grocery", isActive=False

• Code validation: empty string ✗
• Active status: False ✗
• Invalid - skip this coupon

After validation, idx = [0, 1, 3] (indices of valid coupons)

Step 2: Sort the Valid Indices

We sort using the key function lambda i: (businessLine[i], code[i]):

• Index 0: key = ("electronics", "SAVE20")
• Index 1: key = ("grocery", "10OFF")
• Index 3: key = ("pharmacy", "DEAL_5")

Sorting these tuples:

1. First by business line: "electronics" < "grocery" < "pharmacy"
2. Within same business line: sort by code alphabetically

Sorted order: idx = [0, 1, 3] (no change needed as they're already in the correct order)

Step 3: Extract Codes

Using the sorted indices, extract the codes:

• code[0] = "SAVE20"
• code[1] = "10OFF"
• code[3] = "DEAL_5"

Output: ["SAVE20", "10OFF", "DEAL_5"]

The result contains all valid coupon codes, sorted first by business line priority (electronics → grocery → pharmacy), then alphabetically within each category.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m + n × log n) which simplifies to O(n × log n) when m is considered constant.

The algorithm consists of several operations:

• The zip operation and iteration through all elements: O(n)
• For each element, the check function is called which iterates through each character in the code string. If m represents the average length of code strings, this is O(m) per element, resulting in O(n × m) total
• The in operator for checking membership in the bs set: O(1) per element
• The sort operation on the filtered indices: O(k × log k) where k is the number of valid coupons. In the worst case, k = n, giving us O(n × log n)
• The final list comprehension: O(k) which is at most O(n)

The dominant term is O(n × log n) from the sorting operation when the string length m is treated as a constant factor, giving us a final time complexity of O(n × log n).

Space Complexity: O(n)

The space usage includes:

• The idx list which can store up to n indices in the worst case: O(n)
• The bs set with 4 constant elements: O(1)
• The sorting operation may use additional space up to O(n) depending on the implementation
• The final returned list can have up to n elements: O(n)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Business Line Order Matches Alphabetical Order

The current solution relies on the fact that the required business line order ("electronics", "grocery", "pharmacy", "restaurant") happens to match alphabetical order. This is a dangerous assumption that could break if requirements change.

Why it's problematic:

• If a new business line like "automotive" is added, it would incorrectly appear first
• If the required order changes (e.g., "restaurant" should come before "pharmacy"), the code would fail silently
• The code doesn't explicitly enforce the required ordering, making it fragile and unclear

Solution: Create an explicit ordering map for business lines:

def validateCoupons(self, code, businessLine, isActive):
    # Explicit business line ordering
    BUSINESS_ORDER = {
        "electronics": 0,
        "grocery": 1,
        "pharmacy": 2,
        "restaurant": 3
    }
  
    # ... validation code ...
  
    # Sort using explicit ordering
    valid_indices.sort(key=lambda i: (BUSINESS_ORDER[businessLine[i]], code[i]))

2. Not Handling Edge Cases in Code Validation

The validation function might miss certain edge cases or be unclear about what constitutes a valid code.

Potential issues:

• Does a code with only underscores like "___" count as valid?
• Should leading/trailing spaces be considered invalid or trimmed?
• What about codes that are extremely long?

Solution: Add explicit validation rules and document edge cases:

def is_valid_code(coupon_code: str) -> bool:
    # Explicitly handle edge cases
    if not coupon_code or len(coupon_code) > 100:  # Add reasonable length limit
        return False
  
    # Ensure at least one alphanumeric character exists
    has_alphanumeric = False
    for char in coupon_code:
        if char.isalpha() or char.isdigit():
            has_alphanumeric = True
        elif char != "_":
            return False
  
    return has_alphanumeric  # Reject codes with only underscores

3. Performance Issues with Large Datasets

The current character-by-character validation could be inefficient for very long coupon codes or large datasets.

Solution: Use regex for more efficient validation:

import re

class Solution:
    def __init__(self):
        # Compile regex once for reuse
        self.valid_code_pattern = re.compile(r'^[a-zA-Z0-9_]+$')
  
    def is_valid_code(self, coupon_code: str) -> bool:
        return bool(coupon_code and self.valid_code_pattern.match(coupon_code))

This approach is generally faster for longer strings and provides clearer intent about what constitutes a valid code.