#1773

Easy

LeetCode Problem Workspace

Count Items Matching a Rule

Count Items Matching a Rule is an easy problem that tests array and string manipulation with conditions based on specific attributes.

array string

Problem Statement

You are given a 2D array items, where each item contains three strings representing its type, color, and name. You are also given a rule that specifies a ruleKey and ruleValue. The goal is to count how many items from the list match the rule, where the ruleKey can be 'type', 'color', or 'name'.

The rule is considered matched if one of the values in the item (type, color, or name) matches the ruleValue. For example, if the ruleKey is 'color' and the ruleValue is 'blue', you count all items where the color is blue. Return the total number of items that satisfy the rule.

Examples

Example 1

Input: items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], ruleKey = "color", ruleValue = "silver"

Output: 1

There is only one item matching the given rule, which is ["computer","silver","lenovo"].

Example 2

Input: items = [["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], ruleKey = "type", ruleValue = "phone"

Output: 2

There are only two items matching the given rule, which are ["phone","blue","pixel"] and ["phone","gold","iphone"]. Note that the item ["computer","silver","phone"] does not match.

Constraints

1 <= items.length <= 104
1 <= typei.length, colori.length, namei.length, ruleValue.length <= 10
ruleKey is equal to either "type", "color", or "name".
All strings consist only of lowercase letters.

Solution Approach

Iterate through the list

The simplest approach is to iterate through the array items and for each item, check if the corresponding value (type, color, or name) matches the ruleValue based on the ruleKey. This direct checking ensures correctness and clarity.

Optimize the comparison

To improve performance, avoid unnecessary comparisons. For example, once an item matches the ruleKey condition, increment a count without doing any further checks for that item.

Leverage dictionary mapping for ruleKey

To optimize, especially for larger datasets, map the ruleKey to indices (0 for type, 1 for color, 2 for name) and access the respective index directly. This minimizes repetitive string comparison and speeds up execution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the iteration method, typically O(n) where n is the length of the items array. The space complexity is O(1) since no extra space is required apart from the input data and the result counter.

What Interviewers Usually Probe

Candidate should understand how to iterate over arrays and conditionally check string values.
Look for the ability to optimize iterations, such as reducing unnecessary string comparisons.
See if the candidate can efficiently handle larger input sizes through improved algorithms.

Common Pitfalls or Variants

Common pitfalls

Failing to properly match ruleKey to the correct index in the item array, leading to incorrect results.
Not handling edge cases like empty arrays or rules that don't match any item.
Unnecessarily complex solutions that don't take advantage of simple iteration for this problem.

Follow-up variants

What if the ruleKey is dynamic and changes per item, requiring different ruleKey checks for each one?
Consider a variant where you need to count multiple types of rules in one pass, instead of just one rule.
Change the input so that the ruleValue is not a string but a more complex data structure, like a range or set.

FAQ

How can I solve the Count Items Matching a Rule problem efficiently?

Iterate through the array and use conditional checks to match the rule based on the ruleKey and ruleValue. Optimize by reducing redundant checks and using direct index access.

What is the time complexity of the Count Items Matching a Rule problem?

The time complexity is O(n), where n is the number of items, as you iterate through the list once.

What happens if no items match the rule in Count Items Matching a Rule?

The function will return 0, indicating no items matched the given rule.

How do I handle larger inputs in Count Items Matching a Rule?

To handle large inputs efficiently, optimize the iteration by minimizing unnecessary checks and using index mappings instead of string comparisons.

What are the edge cases for Count Items Matching a Rule?

Edge cases include empty arrays, items where no element matches the rule, and scenarios where the ruleKey is not valid or does not match any items.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

class Solution:
    def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
        i = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2)
        return sum(v[i] == ruleValue for v in items)

Continue Practicing

#1769 minimum number of operations to move all balls to each box #1807 evaluate the bracket pairs of a string #1813 sentence similarity iii