Skip to main content
CodePeet

Count Items Matching a Rule

Try it yourself
EasyProblemExternal link

Description

You are given an array items, where items[i] = [type_i, color_i, name_i] describes the type, the color and the name of item i. You are also given a rule made of two strings, ruleKey and ruleValue.

Item i matches the rule when one of these is true:

  • ruleKey == "type" and ruleValue == type_i;
  • ruleKey == "color" and ruleValue == color_i;
  • ruleKey == "name" and ruleValue == name_i.

Return the number of items that match the rule.

Examples

Example 1

Input: items = [["phone", "black", "pixel"], ["laptop", "silver", "thinkpad"], ["phone", "silver", "iphone"], ["tablet", "black", "ipad"]], ruleKey = "color", ruleValue = "silver"

Output: 2

Explanation: Only the colors are compared. Items 1 and 2 are silver; items 0 and 3 are black.

Example 2

Input: the same items, ruleKey = "name", ruleValue = "ipad"

Output: 1

Explanation: Only item 3 is named ipad.

Example 3

Input: the same items, ruleKey = "name", ruleValue = "silver"

Output: 0

Explanation: "silver" appears in the items, but only as a color. The rule asks for items named silver, and there are none.

Constraints

  • 1 ≤ items.length ≤ 10^4
  • 1 ≤ type_i.length, color_i.length, name_i.length, ruleValue.length ≤ 10
  • ruleKey is "type", "color" or "name".
  • All the strings consist only of lowercase letters.

Editorial

Brute Force

Intuition

Go through the items one by one and apply the rule exactly as it is written. If the key is "type", compare the item's type with the value; otherwise, if the key is "color", compare its color; otherwise, if the key is "name", compare its name. Each time a comparison is equal, add 1 to the count.

The four items of Example 1 as a table with columns type, color and name. The rule key "color" frames the color column: items 1 and 2 are silver and match, items 0 and 3 are black. 2 items match.

Only the chosen field counts. The value has to match in the field the key names. In Example 3, "silver" does appear in the items, but only as a color, so a rule asking for the name "silver" matches nothing.

Comparing strings. In Python and C++, == on two strings compares their letters. In Java it does not: == asks whether the two variables point to the very same string object, and a string read from the input is a different object from ruleValue even when the letters are the same. On a real run, comparing two strings that both spell silver gives false with == and true with .equals. Always compare strings with .equals in Java.

Reading items without copying (C++). for (const auto& item : items) looks at each item where it is. Writing for (auto item : items) would copy the item, all three strings, on every round.

Step-by-Step Explanation

We trace Example 1, where the rule is color = silver. The top row is the item being checked, with its fields named underneath; its color is green when it equals silver and orange when it does not.

Step 1: The rule is ruleKey = "color", ruleValue = "silver". count starts at 0.

Step 2: Item 0 (phone, black, pixel): 3 questions about the key, then black is not "silver". count stays 0.

Step 3: Item 1 (laptop, silver, thinkpad): 2 questions about the key, then silver equals "silver", so count = 1.

Step 4: Item 2 (phone, silver, iphone): 2 questions about the key, then silver equals "silver", so count = 2.

Step 5: Item 3 (tablet, black, ipad): 3 questions about the key, then black is not "silver". count stays 2.

Step 6: Return 2, after 10 questions about a key that never changed.

Brute Force — Ask Which Key, for Every Item — Example 1, rule color = silver. Each item is shown with its fields named underneath; the if-chain asks about the key again for every item.

Algorithm

  1. Set count = 0.
  2. For each item [type, color, name]:
    • if ruleKey == "type" and type == ruleValue, add 1 to count;
    • otherwise, if ruleKey == "color" and color == ruleValue, add 1;
    • otherwise, if ruleKey == "name" and name == ruleValue, add 1.
  3. Return count.

Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int count = 0;
        for (const auto& item : items) {  // by reference: copying an item would copy its three strings
            if (ruleKey == "type" && item[0] == ruleValue) count++;
            else if (ruleKey == "color" && item[1] == ruleValue) count++;
            else if (ruleKey == "name" && item[2] == ruleValue) count++;
        }
        return count;
    }
};
class Solution:
    def countMatches(self, items: list[list[str]], ruleKey: str, ruleValue: str) -> int:
        count = 0
        for item_type, color, name in items:
            if ruleKey == 'type' and item_type == ruleValue:
                count += 1
            elif ruleKey == 'color' and color == ruleValue:
                count += 1
            elif ruleKey == 'name' and name == ruleValue:
                count += 1
        return count
import java.util.List;

class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int count = 0;
        for (List<String> item : items) {  // equals compares the letters; == would compare which object it is
            if (ruleKey.equals("type") && item.get(0).equals(ruleValue)) count++;
            else if (ruleKey.equals("color") && item.get(1).equals(ruleValue)) count++;
            else if (ruleKey.equals("name") && item.get(2).equals(ruleValue)) count++;
        }
        return count;
    }
}

Complexity Analysis

Let n be the number of items and L the length of the strings, at most 10.

Time Complexity: O(n · L). Each item costs up to three questions about the key and one comparison of the value, and comparing two strings takes up to L steps.

Space Complexity: O(1).

Why This Approach Is Not Efficient

The answer to "which field does the rule name?" is the same for every item, yet the if-chain asks it again for each one, up to three questions per item. On Example 1 that is 10 questions about the key for 4 items. The growth is already the best possible, O(n), so this is not about big-O: it is repeated work inside the loop. Measured in Python on 10,000 items, it takes 0.155 ms, against 0.071 ms when the key is settled once before the loop.

The key only decides which of an item's three positions to read, and that can be worked out once.

Optimal Approach - Decide the Column Once

Intuition

Turn the key into a position, once. An item is a list of three strings in a fixed order: the type at position 0, the color at position 1, the name at position 2. So the key simply names a position. Look it up before the loop, with a small dictionary in Python, {'type': 0, 'color': 1, 'name': 2}, or a short chain of comparisons in C++ and Java. After that, every item needs just one comparison, item[column] == ruleValue.

Left: the if-chain asks about the key for every item, type? color? name?, 10 questions for 4 items. Right: "color" is turned into column 1 once, and each item needs one comparison of its color with silver.

This pattern, working out before a loop anything that does not change inside it, is worth making a habit. Here it removes every question about the key and leaves the loop doing only the work that really differs from item to item.

In one line. Python can count with sum(1 for item in items if item[column] == ruleValue), and Java streams can do the same with filter and count. The plain loop below does exactly the same work and reads the same in all three languages.

Step-by-Step Explanation

We trace Example 1 again. The first frame turns the key into a position; after that each item needs one comparison, green when it equals silver and orange when it does not.

Step 1: Before the loop: "color" is at position 1, so column = 1.

Step 2: Item 0: item[1] is black, not a match. count stays 0.

Step 3: Item 1: item[1] is silver, a match, so count = 1.

Step 4: Item 2: item[1] is silver, a match, so count = 2.

Step 5: Item 3: item[1] is black, not a match. count stays 2.

Step 6: Return 2, with the key looked up once.

Decide the Column Once, Then One Comparison per Item — Example 1, rule color = silver. The key becomes a position before the loop; each item then needs a single comparison.

Algorithm

  1. Set column to 0, 1 or 2 when ruleKey is "type", "color" or "name".
  2. Set count = 0. For each item, add 1 to count if item[column] == ruleValue.
  3. Return count.

In Java, still .equals, not ==. The position is decided once, but the comparison of the value is still between two different string objects.

Code

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int column = ruleKey == "type" ? 0 : ruleKey == "color" ? 1 : 2;  // decided once: it is the same for every item
        int count = 0;
        for (const auto& item : items)
            if (item[column] == ruleValue) count++;
        return count;
    }
};
class Solution:
    def countMatches(self, items: list[list[str]], ruleKey: str, ruleValue: str) -> int:
        column = {'type': 0, 'color': 1, 'name': 2}[ruleKey]  # decided once: it is the same for every item
        count = 0
        for item in items:
            if item[column] == ruleValue:
                count += 1
        return count
import java.util.List;

class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int column = ruleKey.equals("type") ? 0 : ruleKey.equals("color") ? 1 : 2;  // decided once: it is the same for every item
        int count = 0;
        for (List<String> item : items)
            if (item.get(column).equals(ruleValue)) count++;
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n · L), one string comparison per item. Measured in Python, 0.071 ms for 10,000 items.

Space Complexity: O(1).

No method can do less. An item that is never checked could be a match, so every item has to be looked at, and n comparisons is the least any method can make.