LeetCode 1773 - Count Items Matching a Rule

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to determine how many items in a list satisfy a given rule. Each item is represented as a list of three strings: its type, color, and name. The rule is given as two strings: ruleKey and ruleValue. The ruleKey specifies which attribute of the item to compare (type, color, or name), and the ruleValue specifies the value that attribute must match. The task is to count how many items in the list meet this rule.

The input consists of an array of lists, where each sublist always has three strings. The constraints ensure that the list has at most 10,000 items, and each string has at most 10 characters. This is relatively small, allowing a simple linear scan to be efficient. We are guaranteed that ruleKey will always be one of the three valid keys and all strings are lowercase, so we do not need to handle invalid keys or case differences.

Edge cases that could potentially trip up naive implementations include a ruleValue that does not match any item, or items where multiple attributes share the same string values. The constraints guarantee non-empty input and valid string lengths, so we do not need to handle empty strings or malformed lists.

Approaches

The brute-force approach is straightforward. We iterate over each item, determine which attribute corresponds to the ruleKey, and check if the attribute matches the ruleValue. Each comparison is O(1), and we repeat this for all items. This gives a linear-time solution, which is already efficient given the constraints. There is no need for a more complex algorithm because a linear scan over 10,000 items is very fast.

The key insight is to map the ruleKey to the correct index in the item list: "type" maps to index 0, "color" maps to index 1, and "name" maps to index 2. By doing this mapping once, we avoid repeated conditional checks inside the loop, slightly improving clarity and efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through all items, compare the relevant field
Optimal	O(n)	O(1)	Map `ruleKey` to index, iterate and count matches; same asymptotics but cleaner and easier to read

Algorithm Walkthrough

Create a mapping from ruleKey to the corresponding index in the item list: "type" -> 0, "color" -> 1, "name" -> 2.
Initialize a counter to zero. This will track how many items match the rule.
Determine the index of the attribute to check using the mapping.
Loop over each item in the items list.
For each item, check if the value at the determined index equals ruleValue.
If it matches, increment the counter.
After the loop, return the counter.

Why it works: This works because the mapping ensures we always check the correct attribute. Since each item has exactly three attributes in the same order, and the comparison is exact, every match is counted correctly.

Python Solution

from typing import List

class Solution:
    def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
        # Map ruleKey to the correct index in the sublist
        key_to_index = {"type": 0, "color": 1, "name": 2}
        index = key_to_index[ruleKey]
        
        # Count items that match the rule
        count = 0
        for item in items:
            if item[index] == ruleValue:
                count += 1
        return count

This Python implementation first maps the ruleKey to its corresponding index. Then, we iterate through each item in the input list. By directly indexing into the item with the mapped index, we check for equality with ruleValue. Each match increments the counter, and we return the total count at the end.

Go Solution

func countMatches(items [][]string, ruleKey string, ruleValue string) int {
    keyToIndex := map[string]int{"type": 0, "color": 1, "name": 2}
    index := keyToIndex[ruleKey]
    
    count := 0
    for _, item := range items {
        if item[index] == ruleValue {
            count++
        }
    }
    return count
}

The Go version uses a map to associate ruleKey with the index. We then loop through each item slice and compare the relevant attribute. Go handles slices and string comparison efficiently, so the behavior is identical to Python. Edge cases such as empty slices are implicitly handled since the constraints guarantee that each sublist has exactly three elements.

Worked Examples

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

Item	Index to check	Matches?
["phone","blue","pixel"]	1	No
["computer","silver","lenovo"]	1	Yes
["phone","gold","iphone"]	1	No

Total matches = 1

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

Item	Index to check	Matches?
["phone","blue","pixel"]	0	Yes
["computer","silver","phone"]	0	No
["phone","gold","iphone"]	0	Yes

Total matches = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through each of the n items once
Space	O(1)	Only a fixed-size mapping and a counter are used, independent of input size

Since n <= 10^4, this approach runs very efficiently. No additional data structures that scale with n are needed.

Test Cases

# Provided examples
assert Solution().countMatches([["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]], "color", "silver") == 1
assert Solution().countMatches([["phone","blue","pixel"],["computer","silver","phone"],["phone","gold","iphone"]], "type", "phone") == 2

# No matches
assert Solution().countMatches([["phone","blue","pixel"]], "name", "ipad") == 0

# All match
assert Solution().countMatches([["phone","blue","pixel"],["phone","blue","pixel"]], "type", "phone") == 2

# Single item match
assert Solution().countMatches([["phone","blue","pixel"]], "color", "blue") == 1

# Different positions same value
assert Solution().countMatches([["phone","blue","phone"]], "name", "phone") == 1

Test	Why
Example 1	Validates basic functionality with one match
Example 2	Validates multiple matches
No matches	Ensures zero is returned when no items match
All match	Checks that all items can be counted correctly
Single item match	Validates minimal input handling
Different positions same value	Ensures correct field is compared, not just string equality anywhere

Edge Cases

One important edge case is when no item matches the rule. A naive implementation might assume at least one match exists, but our approach correctly returns zero by initializing the counter to zero. Another edge case is when multiple items have identical values, testing that duplicates are correctly counted individually. Lastly, if the ruleValue appears in other fields but not in the field specified by ruleKey, our implementation correctly ignores those fields and only compares the target field. This prevents overcounting and ensures accuracy.