3606. Coupon Code Validator

EasyArrayHash TableStringSorting

Problem Description

You are given three arrays of length n that describe the properties of n coupons: code, businessLine, and isActive. The ith coupon has:

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 currently active.

A coupon is considered valid if all of the following conditions hold:

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

Return an array of the codes of all valid coupons, sorted first by their businessLine in the order: "electronics", "grocery", "pharmacy", "restaurant", and then by code in lexicographical (ascending) order within each category.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, think about each rule for a valid coupon as a filter. If a coupon passes all the filters (identifier check, valid category, and active status), it should be included in the result. For the rule about identifiers, we need to verify both that the code is not empty and that every character in the code is either a letter, a digit, or an underscore. For business categories, only coupons with one of the exact four allowed categories should be counted. Lastly, only active coupons are valid. After filtering for validity, we need to sort the results by business line in a specified order and, within the same category, by the coupon code alphabetically. Using these direct checks and a custom sorting sequence, we can implement the solution simply and efficiently.

Solution Approach

The solution uses simulation to directly implement the rules stated in the problem:

Identifier Validation: For each coupon, check if the code is non-empty and every character is either a letter (.isalpha()), a digit (.isdigit()), or an underscore (_). This can be done with a helper function that loops through each character.
Business Line Check: Use a set to store the four valid business categories: {"electronics", "grocery", "pharmacy", "restaurant"}. For each coupon, confirm its businessLine value is present in this set.
Active Status Check: Confirm that isActive[i] is True for the coupon.
Collect Valid Coupons: For each coupon that passes all the above checks, collect its index.
Sorting: Sort the valid coupon indices with a two-level sort:
- First, by the order of business line. This is done by assigning an order index to each category (for example, using a mapping like {"electronics": 0, "grocery": 1, "pharmacy": 2, "restaurant": 3}) so sorting follows the required sequence.
- Second, sort by coupon code in lexicographical order within the same business category.
Result Construction: After sorting, extract the codes of the valid coupons in the determined order and return them as the answer.

The overall logic can be described as:

Loop through all coupons and apply all three validity checks.
Store indices of valid coupons.
Sort indices using custom keys for category order and lexicographical code.
Return the list of codes corresponding to these sorted indices.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Suppose we have the following arrays:

code =        ["A1_b", "b2", "C#", "dD3", "E_"]
businessLine = ["grocery", "electronics", "grocery", "restaurant", "electronics"]
isActive =    [True,     True,           False,  True,         True]

Let's apply the steps from the solution approach:

1. Identifier Validation

"A1_b" → valid (letters, digits, underscore, non-empty)
"b2" → valid
"C#" → invalid (contains '#')
"dD3" → valid
"E_" → valid

2. Business Line Check

Valid categories: {"electronics", "grocery", "pharmacy", "restaurant"} All entries except "C#" (which is not filtered out here) are within the valid set.

3. Active Status Check

"C#" has isActive = False: invalid.
The rest have isActive = True.

4. Collect Valid Coupons

Remaining valid coupons (indices):

0: "A1_b", "grocery"
1: "b2", "electronics"
3: "dD3", "restaurant"
4: "E_", "electronics"

5. Sorting

Category order:

"electronics" (0), "grocery" (1), "pharmacy" (2), "restaurant" (3)

Map valid coupons to sorting keys:

1: ("electronics", "b2") → (0, "b2")
4: ("electronics", "E_") → (0, "E_")
0: ("grocery", "A1_b") → (1, "A1_b")
3: ("restaurant", "dD3") → (3, "dD3")

Sort by category, then lex in code:

Within "electronics": "E_" < "b2" (because capital letters come before lowercase in ASCII lex order)

So the order is:

4: "E_" (electronics)
1: "b2" (electronics)
0: "A1_b" (grocery)
3: "dD3" (restaurant)

6. Result Construction

Final sorted valid codes:

["E_", "b2", "A1_b", "dD3"]

Solution Implementation

1from typing import List
2
3class Solution:
4    def validateCoupons(
5        self, code: List[str], businessLine: List[str], isActive: List[bool]
6    ) -> List[str]:
7        # Checks if a coupon code is valid: non-empty and contains only alphanumerics or underscores
8        def is_valid_coupon(s: str) -> bool:
9            if not s:
10                return False
11            for char in s:
12                if not (char.isalnum() or char == "_"):
13                    return False
14            return True
15
16        # Approved business lines
17        allowed_business = {"electronics", "grocery", "pharmacy", "restaurant"}
18        valid_indices = []
19
20        # Iterate over coupon data and collect valid indices
21        for i, (c, b, active) in enumerate(zip(code, businessLine, isActive)):
22            if active and b in allowed_business and is_valid_coupon(c):
23                valid_indices.append(i)
24
25        # Sort indices by businessLine, then code lexicographically
26        valid_indices.sort(key=lambda i: (businessLine[i], code[i]))
27
28        # Return the sorted corresponding codes
29        return [code[i] for i in valid_indices]
30

1class Solution {
2    // Main method to validate coupons based on given arrays
3    public List<String> validateCoupons(String[] codes, String[] businessLines, boolean[] isActive) {
4        List<Integer> validIndices = new ArrayList<>();
5        // Set of allowed business lines
6        Set<String> allowedBusiness = new HashSet<>(Arrays.asList(
7                "electronics", "grocery", "pharmacy", "restaurant"));
8
9        // Iterate through all coupons
10        for (int i = 0; i < codes.length; i++) {
11            // Check if coupon is active, business line is allowed, and code is valid
12            if (isActive[i] && allowedBusiness.contains(businessLines[i]) && isValidCode(codes[i])) {
13                validIndices.add(i);
14            }
15        }
16
17        // Sort indices first by business line, then by code lexicographically
18        validIndices.sort((i, j) -> {
19            int compareBusiness = businessLines[i].compareTo(businessLines[j]);
20            if (compareBusiness != 0) {
21                return compareBusiness;
22            }
23            return codes[i].compareTo(codes[j]);
24        });
25
26        // Collect validated and sorted coupon codes
27        List<String> result = new ArrayList<>();
28        for (int index : validIndices) {
29            result.add(codes[index]);
30        }
31        return result;
32    }
33
34    // Helper method to check if a coupon code is valid (non-empty, only alphanumeric or '_')
35    private boolean isValidCode(String code) {
36        if (code.isEmpty()) {
37            return false;
38        }
39        for (char ch : code.toCharArray()) {
40            if (!Character.isLetterOrDigit(ch) && ch != '_') {
41                return false;
42            }
43        }
44        return true;
45    }
46}
47

1class Solution {
2public:
3    // Returns a list of valid and sorted coupon codes
4    vector<string> validateCoupons(vector<string>& codes, vector<string>& businessLines, vector<bool>& isActives) {
5        vector<int> validIndexes;
6        unordered_set<string> validLines = {"electronics", "grocery", "pharmacy", "restaurant"};
7
8        // Check each coupon for validity
9        for (int i = 0; i < codes.size(); ++i) {
10            const string& currentCode = codes[i];
11            const string& currentLine = businessLines[i];
12            bool currentActive = isActives[i];
13            // Active + valid business line + valid code format
14            if (currentActive && validLines.count(currentLine) && check(currentCode)) {
15                validIndexes.push_back(i);
16            }
17        }
18
19        // Sort by business line, and then by code if business lines are equal
20        sort(validIndexes.begin(), validIndexes.end(), [&](int i, int j) {
21            if (businessLines[i] != businessLines[j]) return businessLines[i] < businessLines[j];
22            return codes[i] < codes[j];
23        });
24
25        vector<string> result;
26        // Construct result using sorted indexes
27        for (int idx : validIndexes) {
28            result.push_back(codes[idx]);
29        }
30        return result;
31    }
32
33private:
34    // Checks if the coupon code is non-empty and contains only alphanumeric characters or underscores
35    bool check(const string& code) {
36        if (code.empty()) return false;
37        for (char ch : code) {
38            if (!isalnum(ch) && ch != '_') {
39                return false;
40            }
41        }
42        return true;
43    }
44};
45

1// Set of valid business line strings
2const validBusinessLines = new Set(['electronics', 'grocery', 'pharmacy', 'restaurant']);
3
4// Helper function to check if a code string is valid
5function isValidCode(s: string): boolean {
6    if (s.length === 0) return false;
7    for (let i = 0; i < s.length; i++) {
8        const c = s[i];
9        // Only alphanumeric and underscore are allowed
10        if (!/[a-zA-Z0-9_]/.test(c)) {
11            return false;
12        }
13    }
14    return true;
15}
16
17// Main function to validate coupons
18function validateCoupons(code: string[], businessLine: string[], isActive: boolean[]): string[] {
19    const validIndices: number[] = [];
20
21    // Collect indices of valid coupons
22    for (let i = 0; i < code.length; i++) {
23        if (
24            isActive[i] &&                                      // Coupon is active
25            validBusinessLines.has(businessLine[i]) &&           // Business line is valid
26            isValidCode(code[i])                                 // Code passes validation
27        ) {
28            validIndices.push(i);
29        }
30    }
31
32    // Sort valid coupons:
33    // 1. By businessLine lexicographically
34    // 2. If same, by code lexicographically
35    validIndices.sort((i, j) => {
36        if (businessLine[i] !== businessLine[j]) {
37            return businessLine[i] < businessLine[j] ? -1 : 1;
38        }
39        return code[i] < code[j] ? -1 : 1;
40    });
41
42    // Return codes of valid coupons, sorted
43    return validIndices.map(i => code[i]);
44}
45

Time and Space Complexity

Time Complexity: The overall time complexity is O(n * log n), where n is the number of coupons. This is because iterating through the lists to filter valid coupons takes O(n) time, and sorting the filtered indices takes O(n * log n) time in the worst case.
Space Complexity: The space complexity is O(n). This includes storing the list of valid coupon indices and the final sorted list of valid coupon codes, both proportional to n in the worst case.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know