#3606

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Coupon Code Validator

The Coupon Code Validator problem requires filtering and sorting coupons based on specific criteria for validity.

Problem Statement

You are given three arrays of length n that describe the properties of n coupons: code, businessLine, and isActive. The ith coupon has a code, a business line it belongs to, and an activation status.

A coupon is considered valid if all of the following conditions hold: isActive[i] must be true, code[i] cannot be empty and must only contain alphanumeric characters or underscores, and businessLine[i] must belong to one of the valid business categories: electronics, grocery, pharmacy, or restaurant. Return an array of the codes of all valid coupons, sorted by their business line in the order: 'electronics', 'grocery', 'pharmacy', 'restaurant', and then by code in lexicographical (ascending) order within each category.

Examples

Example 1

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

Output: ["PHARMA5","SAVE20"]

Example 2

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

Output: ["ELECTRONICS_50"]

Constraints

n == code.length == businessLine.length == isActive.length
1 <= n <= 100
0 <= code[i].length, businessLine[i].length <= 100
code[i] and businessLine[i] consist of printable ASCII characters.
isActive[i] is either true or false.

Solution Approach

Filter Invalid Coupons

Start by filtering out coupons that don't meet the conditions: the code is empty, contains non-alphanumeric/underscore characters, or the business line is invalid. Also, remove coupons with isActive set to false.

Categorize Coupons by Business Line

After filtering, categorize the valid coupons into four groups based on their business line: 'electronics', 'grocery', 'pharmacy', and 'restaurant'. Use a hash table to map business lines to their respective coupon codes.

Sort Coupons

For each category, sort the valid coupon codes lexicographically. After sorting the codes within each business line, concatenate the sorted lists of all categories to get the final result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting step, which is O(n log n) due to the lexicographical sorting of coupon codes. Space complexity is O(n) for storing the filtered and categorized coupons.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of array scanning techniques to efficiently filter out invalid coupons.
Interviewers should look for efficient sorting algorithms, especially when handling multiple categories.
Look for the use of hash tables or similar structures to manage business line categorization.

Common Pitfalls or Variants

Common pitfalls

Failing to handle invalid business lines or misinterpreting the valid categories.
Not properly filtering out non-alphanumeric characters in coupon codes or failing to check if code[i] is empty.
Incorrect sorting logic, such as not sorting coupons correctly within each business line or misordering business lines.

Follow-up variants

Handling a larger number of coupons (n > 100) with the same filtering and sorting approach.
Returning coupons in reverse lexicographical order for each business line.
Allowing different valid business lines and adjusting the sorting order accordingly.

FAQ

What is the Coupon Code Validator problem about?

The problem asks you to filter and sort coupons based on specific conditions like activation status, business line, and code validity.

What is the best approach for solving the Coupon Code Validator problem?

The most efficient approach is to filter invalid coupons, categorize them by business line using a hash table, and then sort them lexicographically within each category.

How should I handle invalid business lines in the Coupon Code Validator problem?

Any coupon with a business line outside of 'electronics', 'grocery', 'pharmacy', or 'restaurant' should be discarded as invalid.

How are the valid coupons sorted in the Coupon Code Validator problem?

Valid coupons are first sorted by business line in the order: 'electronics', 'grocery', 'pharmacy', 'restaurant'. Within each category, they are sorted lexicographically by code.

What are some common mistakes in solving the Coupon Code Validator problem?

Common mistakes include not correctly filtering invalid coupons, failing to check code validity, or incorrectly sorting the coupons by business line or lexicographically.

terminal

Solution

Solution 1: Simulation

We can directly simulate the conditions described in the problem to filter out valid coupons. The specific steps are as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validateCoupons(
        self, code: List[str], businessLine: List[str], isActive: List[bool]
    ) -> List[str]:
        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

        idx = []
        bs = {"electronics", "grocery", "pharmacy", "restaurant"}
        for i, (c, b, a) in enumerate(zip(code, businessLine, isActive)):
            if a and b in bs and check(c):
                idx.append(i)
        idx.sort(key=lambda i: (businessLine[i], code[i]))
        return [code[i] for i in idx]

Continue Practicing

#3143 maximum points inside the square #3035 maximum palindromes after operations #2933 high access employees