Skip to content

Latest commit

 

History

History
85 lines (57 loc) · 3.74 KB

035.md

File metadata and controls

85 lines (57 loc) · 3.74 KB

1773. Count Items Matching a Rule

Difficulty: 🟢 Easy

You are given an array items, where each items[i] = [typei, colori, namei] describes the type, color, and name of the ith item. You are also given a rule represented by two strings, ruleKey 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
Explanation: 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
Explanation: 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.

Solutions

O(n) solution in Python3

class Solution:
    def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
        count = 0
        for type_, color, name in items:
            if ruleKey == "type" and type_ == ruleValue:
                count += 1
            elif ruleKey == "color" and color == ruleValue:
                count += 1
            elif ruleKey == "name" and name == ruleValue:
                count += 1
        return count

The given solution counts the number of items that match the given rule by iterating through the items array and comparing the values of type, color, and name with the ruleValue based on the ruleKey.

The algorithm works as follows:

  1. Initialize a count variable to 0.
  2. Iterate through each item in the items array.
  3. For each item, compare the value of ruleKey with the corresponding value (type, color, or name) of the item:
    • If ruleKey is "type" and the value matches ruleValue, increment the count by 1.
    • If ruleKey is "color" and the value matches ruleValue, increment the count by 1.
    • If ruleKey is "name" and the value matches ruleValue, increment the count by 1.
  4. Return the count, which represents the number of items that match the given rule.

The algorithm compares the values of type, color, and name with ruleValue based on the value of ruleKey and increments the count if there is a match.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the items array. The algorithm iterates through each item in the items array once and performs constant-time operations at each iteration.

The space complexity of the algorithm is O(1) as it uses only a constant amount of extra space to store the count variable.

Summary

The given solution counts the number of items that match the given rule by comparing the values of type, color, and name with ruleValue based on ruleKey. It has a time complexity of O(n) and a space complexity of O(1), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.