3606. Coupon Code Validator
Problem Description
You are given three arrays of length n
that describe the properties of n
coupons: code
, businessLine
, and isActive
. The i
th 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]
istrue
.
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.
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 itsbusinessLine
value is present in this set. -
Active Status Check: Confirm that
isActive[i]
isTrue
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.
- First, by the order of business line. This is done by assigning an order index to each category (for example, using a mapping like
-
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 EvaluatorExample 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)
, wheren
is the number of coupons. This is because iterating through the lists to filter valid coupons takesO(n)
time, and sorting the filtered indices takesO(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 ton
in the worst case.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donโt Miss This!