LeetCode 3606: Coupon Code Validator

Meta Data

#

Difficulty: easy First Attempt: 2025-07-06

• Submissions: Wrong Answer ×4 → Accepted

Approach

#

Two steps:

1. Filter: code non-empty with only letters, digits and underscores; the category is one of the four; isActive is True.
2. Sort: by the given category order, then by code lexicographically. Use (category order, code) as the sort key (Hash Table Template 5), with the category order from a dictionary.

My Attempts

#

The four categories happen to be in alphabetical order, so sorting by the category string also works; a dictionary states the order without relying on that coincidence.

Solution

#

class Solution:
    def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
        order = {"electronics": 0, "grocery": 1, "pharmacy": 2, "restaurant": 3}
        valid = [
            (order[b], c)
            for c, b, active in zip(code, businessLine, isActive)
            if active and b in order and c and all(ch.isalnum() or ch == "_" for ch in c)
        ]
        return [c for _, c in sorted(valid)]

str.isalnum() also returns True for non-ASCII letters; the input here is ASCII only, so that is fine.

Complexity

#

Time O(L + n log n) with L the total code length, space O(n).

Mistakes to Avoid

#

• range(a, b) excludes b.
• With a multi-part sort key, the order of the parts is the priority.

Interview Explanation

#

I filter valid coupons: non-empty code of letters, digits and underscores, a listed category, and active. Then I sort by (category order, code), with the order from a dictionary. Time O(n log n).