1773. Count Items Matching a Rule
Model: qwen2.5-coder:14b
Topics: Array,String
FAANG asked: 1
Acceptance rate: 85.2%
Problem Breakdown
The problem requires counting items in an array that match a given rule. Each item is represented as a list of three strings: type, color, and name. The rule is defined by two strings: ruleKey (which can be “type”, “color”, or “name”) and ruleValue. An item matches the rule if the value corresponding to ruleKey in the item’s list equals ruleValue.
Inputs:
items: A list of lists, where each sublist contains three strings representing an item’s type, color, and name.ruleKey: A string that specifies which attribute of the item to check (“type”, “color”, or “name”).ruleValue: A string that specifies the value to match for the attribute specified byruleKey.
Outputs:
- An integer representing the number of items that match the given rule.
Implicit Constraints/Edge Cases:
- The
ruleKeyis always one of the three valid attributes. - All strings are non-empty and consist only of lowercase letters.
- The length of
itemscan be up to 10,000, so the solution should be efficient in terms of time complexity.
Intuition
A brute-force approach would involve iterating through each item and checking if it matches the rule by comparing the appropriate attribute. This approach is straightforward but has a time complexity of O(n), where n is the number of items, which is acceptable given the constraints.
The key insight is to use a dictionary to map ruleKey to its corresponding index in the item list (0 for “type”, 1 for “color”, and 2 for “name”). This allows us to directly access the correct attribute of each item without needing to check the value of ruleKey multiple times.
Approach
- Create a dictionary
key_to_indexthat maps “type” to 0, “color” to 1, and “name” to 2. - Use this dictionary to get the index corresponding to
ruleKey. - Initialize a counter
countto zero. - Iterate through each item in the
itemslist:- Access the attribute at the index determined by
ruleKey. - If this attribute matches
ruleValue, increment the counter.
- Access the attribute at the index determined by
- Return the counter.
Complexity Analysis
- Time Complexity: O(n), where n is the number of items in the
itemslist. We iterate through each item once. - Space Complexity: O(1). The space used does not depend on the input size; it only includes a fixed-size dictionary and a few variables.
Solution
def countMatches(items, ruleKey, ruleValue):
# Map ruleKey to its corresponding index in the item list
key_to_index = {"type": 0, "color": 1, "name": 2}
# Get the index of the attribute we need to check
index = key_to_index[ruleKey]
# Initialize a counter for matching items
count = 0
# Iterate through each item and check if it matches the rule
for item in items:
if item[index] == ruleValue:
count += 1
return count
Edge Cases Handled
- Empty
itemslist: The function will correctly return 0, as there are no items to match. - All items matching the rule: The counter will increment for each item, returning the total number of items.
- No items matching the rule: The counter will remain 0, returning 0.
- Multiple items with the same attribute value: The function correctly counts all such items.