Count Items Matching a Rule

EASY

Description

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

The i^th item is said to match the rule if one of the following 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 given rule.

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 <= 10⁴
1 <= type_i.length, color_i.length, name_i.length, ruleValue.length <= 10
ruleKey is equal to either "type", "color", or "name".
All strings consist only of lowercase letters.

Approaches

Checkout 3 different approaches to solve Count Items Matching a Rule. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration with Conditional Checks

This approach involves iterating through each item in the items list. Inside the loop, a series of if-else if statements are used to determine which attribute of the item to check based on the ruleKey. This is the most direct and straightforward way to translate the problem's logic into code.

Algorithm

Initialize a counter variable, matchCount, to zero.
Loop through every item in the items list.
Inside the loop, use a series of if-else if statements to check the value of ruleKey:
- If ruleKey is "type", compare item.get(0) with ruleValue. If they match, increment matchCount.
- If ruleKey is "color", compare item.get(1) with ruleValue. If they match, increment matchCount.
- If ruleKey is "name", compare item.get(2) with ruleValue. If they match, increment matchCount.
After the loop finishes, return matchCount.

The core idea is to traverse the entire list of items. For each item, we need to check if it satisfies the given rule. This check involves two conditions: the ruleKey must match the property we are interested in, and the item's value for that property must match the ruleValue. We can implement this with a nested conditional structure inside a loop. We initialize a counter to 0, iterate through the items, and if an item matches the rule, we increment the counter.

class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int count = 0;
        for (List<String> item : items) {
            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

Time Complexity: O(N), where N is the number of items in the list. We iterate through each item once. String comparisons take constant time on average for strings of limited length as per the constraints.Space Complexity: O(1), as we only use a constant amount of extra space for the counter variable.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra data structures.

Cons:

Repeats the ruleKey string comparison in every iteration of the loop, which is slightly inefficient, though the performance impact is negligible in practice.

Code Solutions

Checking out 3 solutions in different languages for Count Items Matching a Rule. Click on different languages to view the code.

class Solution {
public
  int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
    int i = ruleKey.charAt(0) == 't' ? 0 : (ruleKey.charAt(0) == 'c' ? 1 : 2);
    int ans = 0;
    for (var v : items) {
      if (v.get(i).equals(ruleValue)) {
        ++ans;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Count Items Matching a Rule

Data Structures:

ArrayString