LeetCode #3606 — Coupon Code Validator

📝 Introduction

We are given three arrays of length n describing the properties of n coupons:

• code[i]: A string representing the coupon identifier.
• businessLine[i]: A string denoting the business category of the coupon.
• isActive[i]: A boolean indicating whether the coupon is active.

A coupon is valid if:

1. code[i] is non-empty and contains only alphanumeric characters (a-z, A-Z, 0-9) and underscores (_).
2. businessLine[i] is one of the following: "electronics", "grocery", "pharmacy", "restaurant".
3. isActive[i] == true.

We must return an array of valid coupon codes, sorted first by businessLine in the order:

1
electronics → grocery → pharmacy → restaurant

and then by code in lexicographical ascending order within the same category.

💡 Approach & Key Insights

1. Validation:

   • Ensure code[i] is not empty and contains only [a-zA-Z0-9_].
   • Ensure businessLine[i] is in the allowed categories set.
   • Ensure isActive[i] is true.

2. Sorting:

   • Create a custom order mapping for categories:

     1
     electronics → 0, grocery → 1, pharmacy → 2, restaurant → 3

   • Sort first by category order, then lexicographically by code.

3. Output:

   • Extract and return only the coupon codes from the valid list after sorting.

🛠️ Breakdown of Approaches

1️⃣ Brute Force / Naive Approach

• Explanation:
  Loop over all coupons, validate each one, and store valid ones in a list. Sort using default string sorting and then reorder by category.
• Time Complexity: O(n log n) — due to sorting.
• Space Complexity: O(n) — storing valid coupons.

2️⃣ Optimized Approach

• Explanation:
  While validating, store valid coupons as pairs (businessLine, code).
  Sort using a custom comparator that compares category order first, then code.
• Time Complexity: O(n log n) — sorting dominates.
• Space Complexity: O(n) — storing valid coupons.

Example:

1
code         = ["SAVE20", "", "PHARMA5", "SAVE@20"]
2
businessLine = ["restaurant", "grocery", "pharmacy", "restaurant"]
3
isActive     = [true, true, true, true]
4

5
Valid coupons after filtering:
6
[("restaurant", "SAVE20"), ("pharmacy", "PHARMA5")]
7

8
After sorting by category order then code:
9
[("pharmacy", "PHARMA5"), ("restaurant", "SAVE20")]
10

11
Output: ["PHARMA5", "SAVE20"]

📊 Complexity Analysis

📌 Example Walkthroughs & Dry Runs

Example 1:

1
Input:
2
code         = ["SAVE20", "", "PHARMA5", "SAVE@20"]
3
businessLine = ["restaurant", "grocery", "pharmacy", "restaurant"]
4
isActive     = [true, true, true, true]
5

6
Valid after filtering:
7
[("restaurant", "SAVE20"), ("pharmacy", "PHARMA5")]
8

9
Sorted:
10
[("pharmacy", "PHARMA5"), ("restaurant", "SAVE20")]
11

12
Output:
13
["PHARMA5", "SAVE20"]

Example 2:

1
Input:
2
code         = ["GROCERY15", "ELECTRONICS_50", "DISCOUNT10"]
3
businessLine = ["grocery", "electronics", "invalid"]
4
isActive     = [false, true, true]
5

6
Valid after filtering:
7
[("electronics", "ELECTRONICS_50")]
8

9
Output:
10
["ELECTRONICS_50"]

🔗 Additional Resources

• Regular Expressions in Java
• Python: all() function
• C++ isalnum function

Author: Kailash Senthilkumar
Date: 09/08/2025