algoadvance

Leetcode 1773. Count Items Matching a Rule

Problem Statement

In LeetCode problem 1773, you’re given a list of items, where each item is represented as a list of strings. Each item contains exactly three strings in the order: type, color, and name. Additionally, you are provided with a rule represented by two strings: a ruleKey and a ruleValue. The ruleKey can be either “type”, “color”, or “name”.

You need to count the number of items that match the given rule. Specifically, you are to return the number of items for which the value specified by the ruleKey equals the ruleValue.

Example:

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

Clarifying Questions

  1. Q1: Can the list of items be empty?
    • A1: For this problem, the list can be empty, and the function should return 0 in that case.
  2. Q2: Are the values in the items case-sensitive?
    • A2: Yes, comparisons should be case-sensitive.
  3. Q3: Will the ruleKey always be valid?
    • A3: Yes, the ruleKey will always be one of “type”, “color”, or “name”.

Strategy

  1. Mapping ruleKey to Index: Since ruleKey can be “type”, “color”, or “name”, we can map these to indices 0, 1, or 2, respectively.
    • “type” -> 0
    • “color” -> 1
    • “name” -> 2

  2. Iterate Over Items: Iterate over each item in the list and use the mapped index to check if the item’s value at that index equals ruleValue.

  3. Count Matches: Count the number of items matching the rule.

Code

Here’s the code implementing the above-mentioned strategy:

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int index;
        
        // Map ruleKey to the corresponding index
        if (ruleKey == "type") {
            index = 0;
        } else if (ruleKey == "color") {
            index = 1;
        } else {
            index = 2;
        }
        
        int count = 0;
        
        // Iterate through each item and count matches
        for (auto& item : items) {
            if (item[index] == ruleValue) {
                count++;
            }
        }
        
        return count;
    }
};

Time Complexity

The time complexity of this approach is O(n), where n is the number of items in the list. This is because we iterate over each item once.

  1. Determine index mapping: O(1)
  2. Iterating over all items: O(n)
  3. String comparison: O(1) comparison for each string (as the length of the strings is assumed to be small)

Therefore, the overall time complexity is O(n).

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