1773. Count Items Matching a Rule
Problem Description
You have an array called items
where each element represents an item with three properties. Each items[i]
is formatted as [type_i, color_i, name_i]
, containing:
- The type of the item (at index 0)
- The color of the item (at index 1)
- The name of the item (at index 2)
You're also given a filtering rule consisting of two strings:
ruleKey
: specifies which property to check (can be "type", "color", or "name")ruleValue
: specifies the value that property should match
An item matches the rule if:
- When
ruleKey
is "type", the item's type equalsruleValue
- When
ruleKey
is "color", the item's color equalsruleValue
- When
ruleKey
is "name", the item's name equalsruleValue
Your task is to count how many items in the array match the given rule.
The solution cleverly maps the ruleKey
to an index (0 for "type", 1 for "color", 2 for "name") by checking the first character of ruleKey
. It then iterates through all items and counts how many have their value at the corresponding index equal to ruleValue
.
Intuition
The key insight is recognizing that each item is structured as a list with a fixed pattern: [type, color, name]
. This means we can access any property by its index position - type is always at index 0, color at index 1, and name at index 2.
Instead of writing three separate conditional checks for each possible ruleKey
, we can map the rule key directly to its corresponding index. Since "type", "color", and "name" all start with different letters ('t', 'c', 'n'), we can use just the first character to determine which index to check.
Once we know which index to examine, the problem becomes straightforward: iterate through all items and count how many have items[i][index] == ruleValue
. This transforms what could have been multiple if-else statements into a single, elegant comparison.
The beauty of this approach lies in its simplicity - by recognizing the pattern between the rule keys and array indices, we reduce the problem to:
- Map
ruleKey
to an index (0, 1, or 2) - Count items where the value at that index matches
ruleValue
This avoids repetitive code and makes the solution both concise and efficient with O(n)
time complexity where n is the number of items.
Solution Approach
The implementation uses a clever indexing technique to solve this problem efficiently:
Step 1: Map ruleKey to Index
i = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2)
This line determines which index to check in each item:
- If
ruleKey[0] == 't'
(meaning "type"), seti = 0
- If
ruleKey[0] == 'c'
(meaning "color"), seti = 1
- Otherwise (meaning "name"), set
i = 2
We only need to check the first character since "type", "color", and "name" all start with unique letters.
Step 2: Count Matching Items
return sum(v[i] == ruleValue for v in items)
This line uses a generator expression with Python's sum()
function:
- For each item
v
initems
, check ifv[i] == ruleValue
- This comparison returns
True
(counted as 1) orFalse
(counted as 0) sum()
adds up all theTrue
values, giving us the total count
Algorithm Pattern: This solution follows a "map and count" pattern:
- Map the search criteria to a specific position
- Count occurrences that match at that position
Time and Space Complexity:
- Time:
O(n)
where n is the number of items, as we iterate through the list once - Space:
O(1)
as we only use a constant amount of extra space for the index variable
The elegance lies in avoiding multiple if-else branches or dictionary lookups, instead using direct array indexing for maximum efficiency.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example to see how this solution works:
Given:
items = [["phone","blue","pixel"], ["computer","silver","lenovo"], ["phone","gold","iphone"]]
ruleKey = "color"
ruleValue = "silver"
Step 1: Map ruleKey to Index
Since ruleKey = "color"
, we check the first character:
ruleKey[0] = 'c'
- Using our mapping:
i = 1
(because color is at index 1 in each item)
Step 2: Count Matching Items
Now we iterate through each item and check if the value at index 1 equals "silver":
-
First item:
["phone","blue","pixel"]
- Check:
items[0][1] == "silver"
→"blue" == "silver"
→False
(count: 0)
- Check:
-
Second item:
["computer","silver","lenovo"]
- Check:
items[1][1] == "silver"
→"silver" == "silver"
→True
(count: 1)
- Check:
-
Third item:
["phone","gold","iphone"]
- Check:
items[2][1] == "silver"
→"gold" == "silver"
→False
(count: 1)
- Check:
Result: The function returns 1
because exactly one item has "silver" as its color.
Another Quick Example:
If we had ruleKey = "type"
and ruleValue = "phone"
:
- Map:
ruleKey[0] = 't'
→i = 0
- Check each item at index 0:
"phone" == "phone"
→True
"computer" == "phone"
→False
"phone" == "phone"
→True
- Result:
2
items match
This approach elegantly handles all three possible rule keys with a single index lookup and iteration.
Solution Implementation
1class Solution:
2 def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
3 # Determine the index based on the rule key
4 # 'type' -> index 0, 'color' -> index 1, 'name' -> index 2
5 if ruleKey == 'type':
6 index = 0
7 elif ruleKey == 'color':
8 index = 1
9 else: # ruleKey == 'name'
10 index = 2
11
12 # Count items that match the rule value at the determined index
13 matching_count = 0
14 for item in items:
15 if item[index] == ruleValue:
16 matching_count += 1
17
18 return matching_count
19
1class Solution {
2 public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
3 // Determine the index based on the rule key
4 // 0 for "type", 1 for "color", 2 for "name"
5 int ruleIndex;
6 if (ruleKey.charAt(0) == 't') {
7 ruleIndex = 0; // "type" starts with 't'
8 } else if (ruleKey.charAt(0) == 'c') {
9 ruleIndex = 1; // "color" starts with 'c'
10 } else {
11 ruleIndex = 2; // "name" starts with 'n'
12 }
13
14 // Initialize counter for matching items
15 int matchCount = 0;
16
17 // Iterate through each item in the list
18 for (List<String> item : items) {
19 // Check if the item's attribute at the rule index matches the rule value
20 if (item.get(ruleIndex).equals(ruleValue)) {
21 matchCount++;
22 }
23 }
24
25 return matchCount;
26 }
27}
28
1class Solution {
2public:
3 int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
4 // Determine the index based on the rule key
5 // "type" -> index 0, "color" -> index 1, "name" -> index 2
6 int index;
7 if (ruleKey == "type") {
8 index = 0;
9 } else if (ruleKey == "color") {
10 index = 1;
11 } else { // ruleKey == "name"
12 index = 2;
13 }
14
15 // Count items that match the rule
16 // For each item, check if the value at the determined index equals ruleValue
17 return count_if(items.begin(), items.end(),
18 [&](const vector<string>& item) {
19 return item[index] == ruleValue;
20 });
21 }
22};
23
1/**
2 * Counts the number of items that match a given rule
3 * @param items - 2D array where each item is [type, color, name]
4 * @param ruleKey - The attribute to match against ('type', 'color', or 'name')
5 * @param ruleValue - The value to match for the specified attribute
6 * @returns The count of items that match the rule
7 */
8function countMatches(items: string[][], ruleKey: string, ruleValue: string): number {
9 // Map the rule key to its corresponding index in the item array
10 // type -> index 0, color -> index 1, name -> index 2
11 const keyIndex: number = ruleKey === 'type' ? 0 : ruleKey === 'color' ? 1 : 2;
12
13 // Count items where the value at the key index matches the rule value
14 return items.reduce((matchCount: number, currentItem: string[]) => {
15 // Increment count if the item's attribute matches the rule value
16 return matchCount + (currentItem[keyIndex] === ruleValue ? 1 : 0);
17 }, 0);
18}
19
Time and Space Complexity
Time Complexity: O(n)
where n
is the number of items in the input list. The algorithm iterates through each item exactly once using the sum()
function with a generator expression. The index determination based on ruleKey[0]
takes O(1)
time, and for each item, the comparison v[i] == ruleValue
also takes O(1)
time. Therefore, the overall time complexity is linear with respect to the number of items.
Space Complexity: O(1)
constant space. The algorithm only uses a single variable i
to store the index, and the generator expression in sum()
doesn't create any additional data structures - it processes items one at a time. No auxiliary space proportional to the input size is used, making the space complexity constant.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect String Comparison for ruleKey
A common mistake is using substring checking or incorrect comparison logic when determining the index:
Pitfall Example:
# Wrong - using 'in' operator if 'type' in ruleKey: index = 0 elif 'color' in ruleKey: index = 1 else: index = 2
This fails if ruleKey
contains unexpected values or if there's any typo. The 'in' operator is also unnecessarily broad.
Solution: Use exact string comparison or the first character approach:
# Better - exact comparison if ruleKey == 'type': index = 0 elif ruleKey == 'color': index = 1 else: index = 2 # Or use dictionary mapping index_map = {'type': 0, 'color': 1, 'name': 2} index = index_map[ruleKey]
2. Assuming Valid Input Without Validation
The code assumes ruleKey
will always be one of the three valid values and that items will always have exactly 3 elements.
Pitfall Example:
# This crashes if item has fewer than 3 elements for item in items: if item[index] == ruleValue: # IndexError if len(item) < 3 count += 1
Solution: Add validation or use safe indexing:
# Validate item length
for item in items:
if len(item) > index and item[index] == ruleValue:
matching_count += 1
# Or handle with try-except
for item in items:
try:
if item[index] == ruleValue:
matching_count += 1
except IndexError:
continue
3. Case Sensitivity Issues
The comparison item[index] == ruleValue
is case-sensitive, which might not match the intended behavior.
Pitfall Example:
# "Phone" != "phone" - this won't match if item[index] == ruleValue: matching_count += 1
Solution: If case-insensitive matching is needed:
# Convert both to lowercase for comparison if item[index].lower() == ruleValue.lower(): matching_count += 1
4. Inefficient Index Determination
Using multiple if-elif statements or complex logic when a simpler approach exists.
Pitfall Example:
# Overly complex if ruleKey[0] == 't' and ruleKey[1] == 'y': index = 0 elif ruleKey[0] == 'c' and ruleKey[1] == 'o': index = 1 # ... etc
Solution: Use the first character check or a dictionary:
# Concise first-character approach index = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2) # Or readable dictionary approach index = {'t': 0, 'c': 1, 'n': 2}[ruleKey[0]]
Which data structure is used in a depth first search?
Recommended Readings
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
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!