algoadvance

Leetcode 1773. Count Items Matching a Rule

Problem Statement

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 ruleKey could be either “type”, “color”, or “name”. You need to count the number of items that match the given ruleKey and ruleValue.

Example

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

    Output:

    • 1
  2. Input:
    • items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]]
    • ruleKey = "type"
    • ruleValue = "phone"

    Output:

    • 2

Clarifying Questions

  1. What are the possible values for ruleKey?
    • Answer: The possible values are “type”, “color”, and “name”.
  2. Can the items array be empty?
    • Answer: Yes, it can be empty. In such a case, the result will be 0.
  3. Are the values in the items consistent and in a fixed format?
    • Answer: Yes, each item is represented as a list of three strings [type, color, name].

Strategy

  1. Identify the index corresponding to the ruleKey.
    • If ruleKey is “type”, the index is 0.
    • If ruleKey is “color”, the index is 1.
    • If ruleKey is “name”, the index is 2.
  2. Loop through the items list and count the items that match the ruleValue for the specified ruleKey.

Code

Here’s the implementation in Java:

import java.util.List;

public class Solution {
    public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int index = -1;
        if ("type".equals(ruleKey)) {
            index = 0;
        } else if ("color".equals(ruleKey)) {
            index = 1;
        } else if ("name".equals(ruleKey)) {
            index = 2;
        }
        
        int count = 0;
        for (List<String> item : items) {
            if (ruleValue.equals(item.get(index))) {
                count++;
            }
        }
        return count;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of items in the list. This is because we iterate through each item exactly once, performing a constant-time operation for each item.

Explanation

  1. Determining the index:
    • The ruleKey determines which attribute of the items we are interested in (“type” -> index 0, “color” -> index 1, “name” -> index 2).
  2. Counting matches:
    • We iterate over each item in the items list.
    • We check if the attribute at the determined index matches the ruleValue.
    • We keep a count of such matches.
  3. Return the count:
    • After completing the iteration, return the count of items that match the given rule.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI