Skip to content

3606. Coupon Code Validator

SourceWeekly Contest 457 Q1DifficultyEasyRating1312

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:

  1. code[i] is non-empty and consists only of alphanumeric characters (a-z, A-Z, 0-9) and underscores (_).
  2. businessLine[i] is one of the following four categories: "electronics", "grocery", "pharmacy", "restaurant".
  3. 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.

 

Example 1:

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

Output: ["PHARMA5","SAVE20"]

Explanation:

  • First coupon is valid.
  • Second coupon has empty code (invalid).
  • Third coupon is valid.
  • Fourth coupon has special character @ (invalid).

Example 2:

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

Output: ["ELECTRONICS_50"]

Explanation:

  • First coupon is inactive (invalid).
  • Second coupon is valid.
  • Third coupon has invalid business line (invalid).

 

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.

Solutions

Solution 1: Simulation

Thinking

With \(n\le 100\), filtering by the stated rules is enough. A valid coupon has a non-empty identifier of letters, digits, and underscores, a business line among the four allowed values, and an active flag.

Collect qualifying indices, sort them by \((\textit{businessLine},\textit{code})\), then emit the identifiers. The sort keys match the required category order and lexicographic tie-break.

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

  1. Check Identifier: For each coupon's identifier, check whether it is non-empty and contains only letters, digits, and underscores.
  2. Check Business Category: Check whether each coupon's business category belongs to one of the four valid categories.
  3. Check Activation Status: Check whether each coupon is active.
  4. Collect Valid Coupons: Collect the ids of all coupons that satisfy the above conditions.
  5. Sort: Sort the valid coupons by business category and identifier.
  6. Return Result: Return the list of identifiers of the sorted valid coupons.

The time complexity is \(O(n \log n)\), and the space complexity is \(O(n)\), where \(n\) is the number of coupons.

 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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<String> validateCoupons(String[] code, String[] businessLine, boolean[] isActive) {
        List<Integer> idx = new ArrayList<>();
        Set<String> bs
            = new HashSet<>(Arrays.asList("electronics", "grocery", "pharmacy", "restaurant"));

        for (int i = 0; i < code.length; i++) {
            if (isActive[i] && bs.contains(businessLine[i]) && check(code[i])) {
                idx.add(i);
            }
        }

        idx.sort((i, j) -> {
            int cmp = businessLine[i].compareTo(businessLine[j]);
            if (cmp != 0) {
                return cmp;
            }
            return code[i].compareTo(code[j]);
        });

        List<String> ans = new ArrayList<>();
        for (int i : idx) {
            ans.add(code[i]);
        }
        return ans;
    }

    private boolean check(String s) {
        if (s.isEmpty()) {
            return false;
        }
        for (char c : s.toCharArray()) {
            if (!Character.isLetterOrDigit(c) && c != '_') {
                return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<string> validateCoupons(vector<string>& code, vector<string>& businessLine, vector<bool>& isActive) {
        vector<int> idx;
        unordered_set<string> bs = {"electronics", "grocery", "pharmacy", "restaurant"};

        for (int i = 0; i < code.size(); ++i) {
            const string& c = code[i];
            const string& b = businessLine[i];
            bool a = isActive[i];
            if (a && bs.count(b) && check(c)) {
                idx.push_back(i);
            }
        }

        sort(idx.begin(), idx.end(), [&](int i, int j) {
            if (businessLine[i] != businessLine[j]) return businessLine[i] < businessLine[j];
            return code[i] < code[j];
        });

        vector<string> ans;
        for (int i : idx) {
            ans.push_back(code[i]);
        }
        return ans;
    }

private:
    bool check(const string& s) {
        if (s.empty()) return false;
        for (char c : s) {
            if (!isalnum(c) && c != '_') {
                return false;
            }
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func validateCoupons(code []string, businessLine []string, isActive []bool) []string {
    idx := []int{}
    bs := map[string]struct{}{
        "electronics": {},
        "grocery":     {},
        "pharmacy":    {},
        "restaurant":  {},
    }

    check := func(s string) bool {
        if len(s) == 0 {
            return false
        }
        for _, c := range s {
            if !unicode.IsLetter(c) && !unicode.IsDigit(c) && c != '_' {
                return false
            }
        }
        return true
    }

    for i := range code {
        if isActive[i] {
            if _, ok := bs[businessLine[i]]; ok && check(code[i]) {
                idx = append(idx, i)
            }
        }
    }

    sort.Slice(idx, func(i, j int) bool {
        if businessLine[idx[i]] != businessLine[idx[j]] {
            return businessLine[idx[i]] < businessLine[idx[j]]
        }
        return code[idx[i]] < code[idx[j]]
    })

    ans := make([]string, 0, len(idx))
    for _, i := range idx {
        ans = append(ans, code[i])
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function validateCoupons(code: string[], businessLine: string[], isActive: boolean[]): string[] {
    const idx: number[] = [];
    const bs = new Set(['electronics', 'grocery', 'pharmacy', 'restaurant']);

    const check = (s: string): boolean => {
        if (s.length === 0) return false;
        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            if (!/[a-zA-Z0-9_]/.test(c)) {
                return false;
            }
        }
        return true;
    };

    for (let i = 0; i < code.length; i++) {
        if (isActive[i] && bs.has(businessLine[i]) && check(code[i])) {
            idx.push(i);
        }
    }

    idx.sort((i, j) => {
        if (businessLine[i] !== businessLine[j]) {
            return businessLine[i] < businessLine[j] ? -1 : 1;
        }
        return code[i] < code[j] ? -1 : 1;
    });

    return idx.map(i => code[i]);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use std::collections::HashSet;

impl Solution {
    pub fn validate_coupons(
        code: Vec<String>,
        business_line: Vec<String>,
        is_active: Vec<bool>,
    ) -> Vec<String> {
        fn check(s: &str) -> bool {
            if s.is_empty() {
                return false;
            }
            s.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
        }

        let bs: HashSet<&str> = ["electronics", "grocery", "pharmacy", "restaurant"]
            .iter()
            .copied()
            .collect();

        let mut idx: Vec<usize> = Vec::new();
        for i in 0..code.len() {
            if is_active[i] && bs.contains(business_line[i].as_str()) && check(&code[i]) {
                idx.push(i);
            }
        }

        idx.sort_by(|&i, &j| {
            let cmp = business_line[i].cmp(&business_line[j]);
            if cmp == std::cmp::Ordering::Equal {
                code[i].cmp(&code[j])
            } else {
                cmp
            }
        });

        idx.into_iter().map(|i| code[i].clone()).collect()
    }
}

Comments