Leetcode 1773: Count Items Matching a Rule

Input: The input consists of an array `items` containing lists of strings, each representing an item with a type, color, and name. The rule is represented by two strings: `ruleKey` and `ruleValue`.

Example: items = [['laptop', 'black', 'dell'], ['phone', 'blue', 'pixel'], ['tablet', 'gold', 'samsung']], ruleKey = 'color', ruleValue = 'blue'

Constraints:

• 1 <= items.length <= 10^4

• 1 <= typei.length, colori.length, namei.length, ruleValue.length <= 10

• ruleKey is one of 'type', 'color', or 'name'.

• All strings consist only of lowercase letters.

Output: Return the number of items that match the given rule.

Example: Output: 1

Constraints:

• The result should be an integer representing the count of matching items.

Goal: The goal is to iterate over the items and check if they match the rule based on the given `ruleKey` and `ruleValue`.

Steps:

• Identify the index for the ruleKey (0 for 'type', 1 for 'color', 2 for 'name').

• Loop through the items and check if the value at the index corresponding to the ruleKey matches the ruleValue.

• Increment the counter for each match found.

Goal: The solution must handle a variety of input sizes and strings efficiently.

Steps:

• The solution must handle up to 10^4 items in the array.

• All strings should consist only of lowercase alphabetic characters.

Assumptions:

• The input array will contain at least one item.

• The ruleKey will always be one of 'type', 'color', or 'name'.

• Input: items = [['laptop', 'black', 'dell'], ['phone', 'blue', 'pixel'], ['tablet', 'gold', 'samsung']], ruleKey = 'color', ruleValue = 'blue'

• Explanation: In this example, there is only one item that matches the color 'blue', which is the second item ['phone', 'blue', 'pixel'].

• Input: items = [['laptop', 'black', 'dell'], ['phone', 'blue', 'pixel'], ['tablet', 'black', 'samsung']], ruleKey = 'type', ruleValue = 'phone'

• Explanation: In this case, only one item matches the type 'phone', which is the second item ['phone', 'blue', 'pixel'].

Approach: The problem can be solved by iterating through the array of items and checking if each item matches the rule based on the given ruleKey and ruleValue.

Observations:

• The ruleKey indicates which element of the item (type, color, or name) to compare with ruleValue.

• We can solve the problem by simply looping through the items and checking if the value at the ruleKey index matches the ruleValue.

Steps:

• Parse the ruleKey to determine which index (0 for type, 1 for color, 2 for name) to check.

• Iterate over the items and check if the item at the ruleKey index matches the ruleValue.

• Return the count of matching items.

Empty Inputs:

• The input will always contain at least one item, as per the problem constraints.

Large Inputs:

• The solution should efficiently handle up to 10^4 items in the input array.

Special Values:

• If no items match the rule, the result will be 0.

Constraints:

• The input will always be valid as per the problem constraints.

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
    int i;
    if(ruleKey=="type")i=0;
    if(ruleKey=="color")i=1;
    if(ruleKey=="name")i=2;
    
    int ans=0;
    for(int j=0;j<items.size();j++){
        if(items[j][i]==ruleValue)ans++;
    }
    
    return ans;
}

1 : Function Definition

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {

Define the function `countMatches`, which takes a reference to a 2D vector `items`, and two strings `ruleKey` and `ruleValue`, and returns the count of items that match the rule.

2 : Variable Declaration

    int i;

Declare an integer variable `i`, which will hold the index of the matching category based on the `ruleKey`.

3 : Condition Check for 'type'

    if(ruleKey=="type")i=0;

Check if the `ruleKey` is 'type'. If it is, assign `i = 0`, indicating that we are checking the first element (type) in each item.

4 : Condition Check for 'color'

    if(ruleKey=="color")i=1;

Check if the `ruleKey` is 'color'. If it is, assign `i = 1`, indicating that we are checking the second element (color) in each item.

5 : Condition Check for 'name'

    if(ruleKey=="name")i=2;

Check if the `ruleKey` is 'name'. If it is, assign `i = 2`, indicating that we are checking the third element (name) in each item.

6 : Result Initialization

    int ans=0;

Initialize the variable `ans` to 0. This will hold the count of matching items.

7 : Loop Through Items

    for(int j=0;j<items.size();j++){

Start a loop to iterate through each item in the `items` 2D vector.

8 : Match Check

        if(items[j][i]==ruleValue)ans++;

If the current item’s value at the index `i` matches the `ruleValue`, increment the `ans` variable by 1.

9 : Return Statement

    return ans;

Return the result `ans`, which contains the count of items that matched the rule.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we iterate through each item once, where n is the number of items in the input array.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) since we are only using a constant amount of space for the counter.

Leetcode 1773: Count Items Matching a Rule

Explore →