Facebook Pixel

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 equals ruleValue
  • When ruleKey is "color", the item's color equals ruleValue
  • When ruleKey is "name", the item's name equals ruleValue

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Map ruleKey to an index (0, 1, or 2)
  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"), set i = 0
  • If ruleKey[0] == 'c' (meaning "color"), set i = 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 in items, check if v[i] == ruleValue
  • This comparison returns True (counted as 1) or False (counted as 0)
  • sum() adds up all the True values, giving us the total count

Algorithm Pattern: This solution follows a "map and count" pattern:

  1. Map the search criteria to a specific position
  2. 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 Evaluator

Example 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":

  1. First item: ["phone","blue","pixel"]

    • Check: items[0][1] == "silver""blue" == "silver"False (count: 0)
  2. Second item: ["computer","silver","lenovo"]

    • Check: items[1][1] == "silver""silver" == "silver"True (count: 1)
  3. Third item: ["phone","gold","iphone"]

    • Check: items[2][1] == "silver""gold" == "silver"False (count: 1)

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]]
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More