1773. Count Items Matching a Rule


Problem Description

In this problem, we are provided with an array named items, where each element is a list containing strings that represent the type, color, and name of an item in that order (i.e., items[i] = [type_i, color_i, name_i]). We are also given two strings, ruleKey and ruleValue, which represent a rule we should use to match items.

An item matches the rule if one of the following conditions is satisfied:

  • If ruleKey is "type", the type of the item (type_i) should match ruleValue.
  • If ruleKey is "color", the color of the item (color_i) should match ruleValue.
  • If ruleKey is "name", the name of the item (name_i) should match ruleValue.

We need to return the count of items that match the provided rule.

Intuition

The problem can be approached by understanding that the ruleKey will always be one of three options: "type", "color", or "name". Given this, we can determine that each option corresponds to an index in the item's list. "type" corresponds to index 0, "color" to index 1, and "name" to index 2.

Knowing this, the solution approach is straightforward:

  1. Determine the index that ruleKey corresponds to.
  2. Iteratively count the number of items where the element at the determined index matches the ruleValue.

The provided solution translates this intuition into code by first using a conditional expression to find the index (i) that corresponds with the ruleKey. Notice the use of the first character ('t', 'c', or any other) to determine the index. This works because in the context of this problem, the first character of each ruleKey option is unique.

After determining the index, the code uses a generator expression within the sum() function to iterate over each item in items and count how many times the item's element at the index i equals the ruleValue. This gives us the total number of matches, which is what we return as the solution.

Solution Approach

The implementation of the solution uses a simple array iteration and indexing technique. It leverages the built-in sum() function to count the number of matches for the given condition, using a generator expression to avoid creating an intermediary list.

Here's the breakdown of the implementation steps:

  1. Determine the index for comparison based on ruleKey:
    • We need to compare the item's type, color, or name based on the ruleKey. Since these attributes are in a fixed order within each item ([type_i, color_i, name_i]), we map the ruleKey to an index:
      • "type" -> 0
      • "color" -> 1
      • "name" -> 2
    • This is accomplished using a simple conditional expression:
1i = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2)
  1. Count the number of items that match ruleValue at the determined index:
    • We then iterate over each item in the items list and increase the count when the element at the index i is equal to ruleValue.
    • This is done using the sum() function and a generator expression, which succinctly combines iteration and condition checking:
1return sum(v[i] == ruleValue for v in items)
  • The generator expression (v[i] == ruleValue for v in items) iterates through each item v in items, checking whether the element at index i equals ruleValue. For each item where the condition is true, the expression yields True, which is numerically equivalent to 1.
  • The sum() function then adds up all the 1s, effectively counting the number of True instances, thus giving us the total count of matching items.

In terms of algorithms and data structures, the solution uses linear search, which is appropriate since there are no constraints that would benefit from a more complex searching algorithm. The algorithm's time complexity is O(n), where n is the number of items in the items list, as every item must be checked against the rule. The space complexity is O(1) since the solution does not allocate additional space proportional to the input size; it only uses a few variables for counting and storing the index.

Example Walkthrough

Let's take the following example to illustrate the solution approach:

Suppose we have an array of items where each item is described by its type, color, and name:

1items = [["phone", "blue", "pixel"], ["computer", "silver", "lenovo"], ["phone", "gold", "iphone"]]

And our task is to count how many items match the rule consisting of ruleKey = "color" and ruleValue = "silver".

According to the approach:

  1. First, we determine the comparison index from the ruleKey.

    • Since ruleKey is "color", we are interested in the second element of each item, which corresponds to index 1 (since indexing starts at 0).
    • Following the provided code snippet, we would get i = 1 because ruleKey[0] is 'c', corresponding to "color".
  2. Next, we iterate over each item and count the occurrences where the item's color matches "silver":

    • We check each item's element at index 1 to see whether it equals "silver".
    • From our example array items, only the second item (["computer", "silver", "lenovo"]) has "silver" as its color at index 1.

Using a generator expression within the sum() function, we effectively iterate with the condition:

1count = sum(item[1] == "silver" for item in items)

This gives us:

1count = sum(True for ["computer", "silver", "lenovo"])
  • Since "silver" matches the only "silver" in our items, the sum() function calculates the sum of 1 instance (True), resulting in count = 1.

Therefore, in this example, the number of items that match the rule ("color", "silver") is 1.

Python Solution

1class Solution:
2    def count_matches(self, items: List[List[str]], rule_key: str, rule_value: str) -> int:
3        # Determine index based on the first character of rule_key
4        # 0 for 'type', 1 for 'color', and 2 for 'name'
5        index = 0 if rule_key[0] == 't' else (1 if rule_key[0] == 'c' else 2)
6      
7        # Count and return how many items match the given rule
8        # Loop through each item in items list and check if the
9        # element at the determined index matches the rule_value
10        return sum(item[index] == rule_value for item in items)
11

Java Solution

1class Solution {
2    // Counts the number of matching items based on the given rule key and rule value.
3    // @param items List of items where each item is represented as a List of Strings with a specific order [type, color, name].
4    // @param ruleKey The rule key representing the attribute by which we want to match (type, color, or name).
5    // @param ruleValue The value we want to match against the selected attribute.
6    // @return The count of items that match the specified rule.
7    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
8        // Determine which attribute (0 for type, 1 for color, 2 for name) we need to check based on the ruleKey.
9        int attributeIndex = "type".equals(ruleKey) ? 0 : ("color".equals(ruleKey) ? 1 : 2);
10      
11        // Initialize a counter for the number of matches.
12        int matchCount = 0;
13      
14        // Iterate through all the items in the list.
15        for (List<String> item : items) {
16            // Check if the current item's attribute matches the ruleValue.
17            if (item.get(attributeIndex).equals(ruleValue)) {
18                // If it matches, increment the count of matches.
19                matchCount++;
20            }
21        }
22      
23        // Return the final count of matches.
24        return matchCount;
25    }
26}
27

C++ Solution

1#include <vector> // Include necessary header for vector
2#include <algorithm> // Include necessary header for count_if function
3
4class Solution {
5public:
6    // Function to count matches of items based on ruleKey and ruleValue.
7    // @param items: a 2D vector containing item information
8    // @param ruleKey: the key to match (type, color, or name)
9    // @param ruleValue: the value to match with the ruleKey
10    // @return: count of items that match the criterion
11    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
12        // Determine the index based on the ruleKey. "type" corresponds to index 0, "color" to 1, "name" to 2.
13        int index;
14        if (ruleKey == "type") {
15            index = 0; // Index for type
16        } else if (ruleKey == "color") {
17            index = 1; // Index for color
18        } else {
19            index = 2; // Index for name
20        }
21
22        // Use count_if algorithm to count elements satisfying a condition
23        // The condition is that the specified field of an item matches the ruleValue
24        int matchCount = count_if(items.begin(), items.end(), [&](const auto& item) {
25            return item[index] == ruleValue;
26        });
27
28        return matchCount; // Return the total count of matches
29    }
30};
31

Typescript Solution

1// Define the type for the item list which is an array of arrays of strings.
2type ItemList = string[][];
3
4/**
5 * Counts the matches of items based on a given rule.
6 * 
7 * @param {ItemList} items - The array of items. Each item is an array containing properties like type, color, and name.
8 * @param {string} ruleKey - The key of the rule which can be 'type', 'color', or 'name'.
9 * @param {string} ruleValue - The value of the rule to match against the items' properties.
10 * @returns {number} The count of items that match the rule.
11 */
12function countMatches(items: ItemList, ruleKey: string, ruleValue: string): number {
13    // Determine the index associated with the ruleKey.
14    // 0 for 'type', 1 for 'color', and 2 for 'name'.
15    const ruleIndex: number = ruleKey === 'type' ? 0 : ruleKey === 'color' ? 1 : 2;
16  
17    // Use the reduce function to iterate over the items and increment the count
18    // based on whether the item property at ruleIndex matches the ruleValue.
19    return items.reduce((count: number, item: string[]) => (
20        count + (item[ruleIndex] === ruleValue ? 1 : 0)
21    ), 0); // Initialize the count as 0.
22}
23

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the number of items in the input list. This is because the code iterates once over all the items, checking whether the value at a certain index matches the ruleValue. The index i is determined based on the initial character of the ruleKey, which is a constant-time operation.

The space complexity is O(1) (constant space) because aside from the space taken by the input, the code uses a fixed amount of extra space - the variable i and the space for the generator expression inside the sum function. No additional space that scales with the input size is used.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫