LeetCode 3606 - Coupon Code Validator

The problem is asking us to validate a set of coupons based on three criteria: the coupon code must be a non-empty string containing only alphanumeric characters or underscores, the business line must belong to a set of four predefined categories, and the coupon must be active.

leetcodeeasyarrayhash-tablestringsorting

LeetCode Problem 3606

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String, Sorting

Solution

Problem Understanding

The problem is asking us to validate a set of coupons based on three criteria: the coupon code must be a non-empty string containing only alphanumeric characters or underscores, the business line must belong to a set of four predefined categories, and the coupon must be active. We are given three arrays of equal length, code, businessLine, and isActive, where the ith element of each array corresponds to the same coupon.

The expected output is a list of coupon codes that pass all validation rules, sorted first by businessLine in a fixed order: "electronics", "grocery", "pharmacy", "restaurant", and then by code lexicographically within each category.

Constraints tell us the input size is small (1 <= n <= 100), so we do not need extremely optimized algorithms, but we do need to carefully check string validity and sorting rules. Important edge cases include empty strings, codes with invalid characters, inactive coupons, invalid business lines, and duplicate coupon codes.

Approaches

The brute-force approach is straightforward. We can iterate over all coupons and, for each coupon, check if it meets the three validation criteria. If it does, we add it to a list. Once all valid coupons are collected, we sort the list first by business line according to the predefined order, and then lexicographically by code. This approach works correctly because it directly implements the problem statement, but it requires careful handling of string validation and sorting with custom rules.

The optimal approach uses the same basic steps but leverages a hash map to assign each business line a priority number for sorting. This avoids repeatedly comparing strings during sorting and allows us to perform a single sort operation efficiently with a tuple key (priority, code).

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Iterate over all coupons, filter invalid ones, then sort with custom comparator
Optimal O(n log n) O(n) Assign numeric priorities to business lines, filter valid coupons, sort tuples by (priority, code)

Algorithm Walkthrough

  1. Define allowed business lines and their priorities. Create a hash map that maps "electronics" → 0, "grocery" → 1, "pharmacy" → 2, "restaurant" → 3. This ensures a consistent, numeric order for sorting.
  2. Initialize a list to hold valid coupons. Each element in this list will be a tuple (priority, code) for easier sorting later.
  3. Iterate over all coupons. For each coupon, check the three conditions:
  • The code is non-empty and contains only alphanumeric characters or underscores. We can use a regular expression or string checks for this.
  • The businessLine exists in the predefined hash map.
  • isActive is True.
  1. Add valid coupons to the list. For each valid coupon, store a tuple of its business line priority and code.
  2. Sort the list of valid coupons. Use the tuple (priority, code) as the key so that the list is first sorted by business line and then by code lexicographically.
  3. Extract the coupon codes from the sorted list. Return the list of strings as the final output.

Why it works: By filtering out invalid coupons and encoding business line priorities numerically, we guarantee that the final sort respects both the required business line order and lexicographical order. The tuple key preserves the invariant that business line comes first in ordering. The problem asks us to filter and sort a list of coupons based on multiple validation rules. We are given three parallel arrays of length n: code, businessLine, and isActive. Each index i represents a coupon with three attributes. A coupon is valid only if its code is non-empty and contains only alphanumeric characters or underscores, its businessLine is one of "electronics", "grocery", "pharmacy", or "restaurant", and it is active (isActive[i] is true).

The expected output is a list of all valid coupon codes, sorted first by business line in the specific order: "electronics", "grocery", "pharmacy", "restaurant", and then by the code in lexicographical ascending order within each business line.

The input constraints indicate that n is at most 100, so performance is not a major concern. Each string length is at most 100. The problem guarantees that all arrays are the same length and contain valid strings or booleans. Edge cases that could cause naive implementations to fail include empty strings, strings with invalid characters, invalid business lines, inactive coupons, or combinations of these. Sorting stability and the custom order of business lines are also subtle points to handle.

Approaches

The brute-force approach would iterate through each coupon and check all validation rules one by one. If valid, we could append the code to a list, then sort the list first by business line using a custom mapping and then by code lexicographically. This works correctly but manually managing the business line ordering during sort can be tedious.

The optimal approach uses a hash map or dictionary to associate business lines with their sort order, filters valid coupons, and then sorts them using a single sort call with a custom key. This takes advantage of Python or Go’s built-in stable sort and allows clear, concise handling of both the business line priority and lexicographic order.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Check each coupon individually, then sort with a custom comparator.
Optimal O(n log n) O(n) Filter valid coupons and sort once using a custom key mapping for business line order and code.

Algorithm Walkthrough

  1. Initialize business line priority mapping: Assign each valid business line a numeric rank corresponding to the desired sort order: "electronics" = 0, "grocery" = 1, "pharmacy" = 2, "restaurant" = 3. This allows easy sorting by category.
  2. Iterate through all coupons: For each index i from 0 to n-1, perform the validation checks.
  3. Validate code: Ensure the code is non-empty and contains only alphanumeric characters or underscores. This can be checked with a regular expression or string method.
  4. Validate business line: Check if businessLine[i] exists in the priority mapping.
  5. Validate activity: Check if isActive[i] is true.
  6. Collect valid coupons: If all conditions are met, append a tuple (businessLine[i], code[i]) to a list of valid coupons.
  7. Sort coupons: Use the priority mapping and the coupon code as a sort key. The sorting key is (priority[businessLine], code).
  8. Return result: Extract only the coupon codes from the sorted list of tuples.

Why it works: The algorithm ensures that only valid coupons are included. Sorting by the numeric priority guarantees the business line order, and lexicographic sorting ensures codes within each category are in ascending order. All operations are performed on at most n elements, and the sort is stable and efficient.

Python Solution

import re
from typing import List

class Solution:
    def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
        # Define allowed business lines and their sort priority
        priority_map = {
from typing import List
import re

class Solution:
    def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
        # Define business line priority mapping
        priority = {
            "electronics": 0,
            "grocery": 1,
            "pharmacy": 2,
            "restaurant": 3
        }
        
        valid_coupons = []
        pattern = re.compile(r'^[A-Za-z0-9_]+$')
        
        for c, b, a in zip(code, businessLine, isActive):
            if a and b in priority_map and c and pattern.fullmatch(c):
                valid_coupons.append((priority_map[b], c))
        
        # Sort by priority and then code lexicographically
        valid_coupons.sort(key=lambda x: (x[0], x[1]))
        
        # Extract only the coupon codes
        return [c for _, c in valid_coupons]

The solution first creates a hash map for business line priorities and a regex pattern to check valid codes. We iterate through the coupons using zip for clean iteration. Valid coupons are stored as tuples of (priority, code) to allow a single sort to handle both business line and code order. The final output is the list of codes after sorting. # Prepare regex for valid coupon code valid_code_pattern = re.compile(r'^[a-zA-Z0-9_]+$')

    valid_coupons = []
    
    # Filter valid coupons
    for c, b, active in zip(code, businessLine, isActive):
        if active and c and b in priority and valid_code_pattern.match(c):
            valid_coupons.append((b, c))
    
    # Sort by business line priority and then by code lexicographically
    valid_coupons.sort(key=lambda x: (priority[x[0]], x[1]))
    
    # Extract sorted coupon codes
    return [c for _, c in valid_coupons]


The solution first defines a priority mapping for business lines to ensure the required sort order. It compiles a regular expression to validate codes. During iteration, it checks all validation rules, appends valid coupons as tuples, and finally sorts them using a custom key that respects both business line order and lexicographical code order. The result is extracted cleanly by selecting only the codes from the sorted tuples.

## Go Solution

```go
import (
    "regexp"
    "sort"
)

func validateCoupons(code []string, businessLine []string, isActive []bool) []string {
    priorityMap := map[string]int{
        "electronics": 0,
        "grocery": 1,
        "pharmacy": 2,
        "restaurant": 3,
    }
    
    pattern := regexp.MustCompile(`^[A-Za-z0-9_]+$`)
    
    type coupon struct {
        priority int
        code     string
    }
    
    var validCoupons []coupon
    
    for i := 0; i < len(code); i++ {
        if isActive[i] && priorityMap[businessLine[i]] >= 0 && code[i] != "" && pattern.MatchString(code[i]) {
            validCoupons = append(validCoupons, coupon{priorityMap[businessLine[i]], code[i]})
    priority := map[string]int{
        "electronics": 0,
        "grocery":     1,
        "pharmacy":    2,
        "restaurant":  3,
    }
    
    validCodePattern := regexp.MustCompile(`^[a-zA-Z0-9_]+$`)
    type coupon struct {
        code string
        line string
    }
    
    validCoupons := []coupon{}
    
    for i := 0; i < len(code); i++ {
        if isActive[i] && code[i] != "" && priority[businessLine[i]] != 0 && validCodePattern.MatchString(code[i]) {
            if _, ok := priority[businessLine[i]]; ok {
                validCoupons = append(validCoupons, coupon{code[i], businessLine[i]})
            }
        }
    }
    
    sort.Slice(validCoupons, func(i, j int) bool {
        if validCoupons[i].priority != validCoupons[j].priority {
            return validCoupons[i].priority < validCoupons[j].priority
        }
        return validCoupons[i].code < validCoupons[j].code
    })
    
    result := make([]string, len(validCoupons))
    for i, c := range validCoupons {
        result[i] = c.code
    }
    
        if priority[validCoupons[i].line] == priority[validCoupons[j].line] {
            return validCoupons[i].code < validCoupons[j].code
        }
        return priority[validCoupons[i].line] < priority[validCoupons[j].line]
    })
    
    result := []string{}
    for _, c := range validCoupons {
        result = append(result, c.code)
    }
    return result
}

In Go, we define a struct coupon to hold priority and code, use a compiled regex for validation, and sort using sort.Slice with a custom comparator. We preallocate the result slice at the end.

Worked Examples

Example 1:

Input: code = ["SAVE20","","PHARMA5","SAVE@20"], businessLine = ["restaurant","grocery","pharmacy","restaurant"], isActive = [true,true,true,true]

Step Coupon Valid? Priority Notes
1 "SAVE20", "restaurant", true Yes 3 Passes all checks
2 "", "grocery", true No - Empty code
3 "PHARMA5", "pharmacy", true Yes 2 Passes all checks
4 "SAVE@20", "restaurant", true No - Invalid character '@'

After sorting by priority and code: ["PHARMA5", "SAVE20"]

Example 2:

Input: code = ["GROCERY15","ELECTRONICS_50","DISCOUNT10"], businessLine = ["grocery","electronics","invalid"], isActive = [false,true,true]

Step Coupon Valid? Priority Notes
1 "GROCERY15", "grocery", false No - Inactive
2 "ELECTRONICS_50", "electronics", true Yes 0 Valid
3 "DISCOUNT10", "invalid", true No - Invalid business line
In Go, we handle validation similarly to Python but use a slice of structs to represent valid coupons. The regexp package validates codes, and sort.Slice with a custom comparison handles sorting. Note the need to explicitly extract the sorted codes at the end, and the handling of Go's map existence check prevents invalid business lines from being included.

Worked Examples

Example 1

Input:

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

Step-by-step:

i code[i] businessLine[i] isActive[i] Valid? Action
0 "SAVE20" "restaurant" true Yes Append ("restaurant", "SAVE20")
1 "" "grocery" true No Skip
2 "PHARMA5" "pharmacy" true Yes Append ("pharmacy", "PHARMA5")
3 "SAVE@20" "restaurant" true No Skip

Sort by business line priority and code:

("pharmacy", "PHARMA5") comes before ("restaurant", "SAVE20")

Output: ["PHARMA5","SAVE20"]

Example 2

Input:

code = ["GROCERY15","ELECTRONICS_50","DISCOUNT10"], businessLine = ["grocery","electronics","invalid"], isActive = [false,true,true]

Step-by-step:

i code[i] businessLine[i] isActive[i] Valid? Action
0 "GROCERY15" "grocery" false No Skip
1 "ELECTRONICS_50" "electronics" true Yes Append ("electronics", "ELECTRONICS_50")
2 "DISCOUNT10" "invalid" true No Skip

Output: ["ELECTRONICS_50"]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Iterate through n coupons (O(n)) and sort valid coupons (O(n log n))
Space O(n) Store valid coupons in a list of size up to n

The solution efficiently handles small n (<= 100) and leverages tuple sorting or custom comparator sorting for clarity and correctness.

Test Cases

# Provided examples
assert Solution().validateCoupons(
    ["SAVE20","","PHARMA5","SAVE@20"], 
    ["restaurant","grocery","pharmacy","restaurant"], 
    [True,True,True,True]
) == ["PHARMA5","SAVE20"]  # mixed valid/invalid codes

assert Solution().validateCoupons(
    ["GROCERY15","ELECTRONICS_50","DISCOUNT10"], 
    ["grocery","electronics","invalid"], 
    [False,True,True]
) == ["ELECTRONICS_50"]  # inactive and invalid business line

# Edge cases
assert Solution().validateCoupons([], [], []) == []  # empty input
assert Solution().validateCoupons(
    ["_A1","B2"], ["electronics","restaurant"], [True, True]
) == ["_A1","B2"]  # underscore allowed
assert Solution().validateCoupons(
    ["A!","B@"], ["electronics","restaurant"], [True, True]
) == []  #

| Time | O(n log n) | Filtering valid coupons is O(n), sorting valid coupons is O(n log n). | | Space | O(n) | Storing valid coupons in a separate list requires O(n) space. |

Even though n is small, using the filtering + sorting approach is efficient and readable. The regex match is O(L) for string length L, but L ≤ 100, so it