Leetcode – Count Items Matching a Rule Solution

Spread the love

The “Count Items Matching a Rule” problem is a classic example of how arrays and simple loops can be used to solve a practical problem. This problem is relatively straightforward but provides a great exercise for practicing basic data manipulation and conditional logic in Python. In this extensive article, we will cover multiple ways to tackle this problem, each with its own time and space complexity analysis.

Problem Statement

You are given an array of items, where each items[i] is of the form ["typei", "colori", "namei"] describing the type, color, and name of the ith item. You are also given a rule represented as a triplet of strings, ruleKey (either “type”, “color”, or “name”) and ruleValue.

The ith item is said to match the rule if one of the following is true:

  • ruleKey == “type” and ruleValue == typei
  • ruleKey == “color” and ruleValue == colori
  • ruleKey == “name” and ruleValue == namei

Return the number of items that match the given rule.

Examples:

Example 1:

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

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

Approach 1: Simple Iteration Method

The most straightforward method to solve this problem is to iterate through the items array and check each element against the given ruleKey and ruleValue.

Algorithm Steps:

  1. Map the ruleKey to its corresponding index. In Python, this is often done with a dictionary.
  2. Initialize a counter variable to 0.
  3. Loop through all the items.
  4. If the item matches the ruleValue based on the ruleKey, increment the counter.
  5. Return the counter value.

Python Code:

def countMatches(items, ruleKey, ruleValue):
    rule_dict = {'type': 0, 'color': 1, 'name': 2}
    rule_index = rule_dict[ruleKey]
    count = 0
    for item in items:
        if item[rule_index] == ruleValue:
            count += 1
    return count

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the items list.
  • Space Complexity: O(1), as we are using only a constant amount of extra space.

Approach 2: Using Python List Comprehension

Python offers powerful list comprehension methods that could make the code more compact and Pythonic.

Python Code:

def countMatches(items, ruleKey, ruleValue):
    rule_dict = {'type': 0, 'color': 1, 'name': 2}
    return sum(1 for item in items if item[rule_dict[ruleKey]] == ruleValue)

Time and Space Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Approach 3: Using Python’s filter Function

Python’s filter function can also be used to solve this problem. While this doesn’t offer any computational advantages, it provides a different way to approach the problem.

Python Code:

def countMatches(items, ruleKey, ruleValue):
    rule_dict = {'type': 0, 'color': 1, 'name': 2}
    return len(list(filter(lambda x: x[rule_dict[ruleKey]] == ruleValue, items)))

Time and Space Complexity:

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n), due to the list created by the filter function.

Approach 4: Using Counter from Python’s collections

Another way to approach this problem is by counting the occurrences of each unique value for the given key using Python’s Counter class from the collections module.

Python Code:

from collections import Counter

def countMatches(items, ruleKey, ruleValue):
    rule_dict = {'type': 0, 'color': 1, 'name': 2}
    counter = Counter(item[rule_dict[ruleKey]] for item in items)
    return counter[ruleValue]

Time and Space Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(u), where u is the number of unique values for the given key.

Conclusion

The “Count Items Matching a Rule” problem is a relatively simple problem that serves as a good starting point for learning about list manipulations, mapping, and basic data structures in Python. Despite its simplicity, there are multiple ways to solve it, each showcasing different features of the Python language.

Leave a Reply