1773. Count Items Matching a Rule - Solution

Q: Is Count Items Matching a Rule easy or hard?

Count Items Matching a Rule is classified as Easy on LeetCode with a high acceptance rate above 80%. The problem mainly tests basic array traversal, string comparison, and conditional logic.

Q: Count Items Matching a Rule Python/Java solution

Both Python and Java implementations follow the same idea: determine the index for the ruleKey, iterate through the items list, and count matches. The algorithm uses a simple loop and string equality check, giving O(n) time and O(1) space complexity.

Q: How to solve Count Items Matching a Rule in O(n)?

Map the ruleKey to its attribute index: type → 0, color → 1, name → 2. Iterate through each item and check if items[i][index] equals ruleValue. Increment a counter whenever the condition is true. The single pass over the array ensures O(n) time complexity.

Q: What is the best approach for Count Items Matching a Rule?

The index mapping method is the cleanest approach. Convert the ruleKey (type, color, or name) into its corresponding index in the item array, then iterate once through the list and compare values. This runs in O(n) time with O(1) extra space and keeps the loop logic simple.

Q: Is Count Items Matching a Rule asked at Google/Amazon/Meta?

This problem is an entry-level array and string filtering question commonly used in screening rounds or practice sets. Variants of attribute filtering appear in interviews at companies like Amazon and Google to test iteration, indexing, and conditional logic.

Q: What data structure is used in Count Items Matching a Rule?

The core data structure is a 2D array (or list of lists) containing string attributes. The solution mainly uses array traversal and string comparison. No additional structures like hash maps are required for the optimal approach.

Q: What is the time complexity of Count Items Matching a Rule?

The optimal solution runs in O(n) time because the algorithm scans the list of items exactly once. Each comparison is constant time. Space complexity is O(1) since only a counter and a few variables are used.

The problem

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.

Approach overview

Problem Overview: You receive a list of items where each item contains three attributes: type, color, and name. Given a ruleKey and ruleValue, count how many items have the matching attribute value.

Approach 1: Index Mapping Method (O(n) time, O(1) space)

Each item is stored as an array of three strings. The position of each attribute is fixed: type → 0, color → 1, and name → 2. Map the incoming ruleKey to its corresponding index, then iterate through the items and compare items[i][index] with ruleValue. Increment a counter whenever they match. The key insight is converting the string key into a constant index so each check becomes a direct array lookup.

This approach performs a single pass through the input, making the time complexity O(n) where n is the number of items. No additional data structures are required, so space complexity remains O(1). It works well when the attribute positions are fixed and known in advance.

Approach 2: Direct Attribute Matching (O(n) time, O(1) space)

Instead of mapping indices, evaluate the rule condition directly during iteration. For each item, check the relevant attribute using conditional logic: compare item[0] when ruleKey == "type", item[1] for "color", and item[2] for "name". Increment the count when the chosen attribute equals ruleValue. This keeps the logic explicit and easy to read.

The algorithm still scans the array once, giving O(n) time complexity with O(1) extra space. Because there are only three possible attributes, the conditional checks are constant time and do not affect scalability.

Both methods rely on straightforward iteration over a array and comparison of string values. No advanced data structures are needed, which is why the problem is categorized as Easy.

Recommended for interviews: The Index Mapping Method is typically preferred. It separates rule interpretation from the main loop and keeps the iteration logic clean. Interviewers expect a linear scan with constant extra space. Showing the direct conditional approach first demonstrates understanding, but the index mapping version looks cleaner and scales better if more attributes are added.

Approach 1: Index Mapping Method

In this approach, we map the ruleKey to its corresponding index in the item list: 'type' maps to index 0, 'color' maps to index 1, and 'name' maps to index 2. We iterate through the items and count how many of them match the ruleValue at the mapped index.

Python

def countMatches(items, ruleKey, ruleValue):
    index = 0 if ruleKey == 'type' else 1 if ruleKey == 'color' else 2
    count = 0
    for item in items:
        if item[index] == ruleValue:
            count += 1
    return count

items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]]
ruleKey = "color"
ruleValue = "silver"
print(countMatches(items, ruleKey, ruleValue))

Java

import java.util.List;

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

C++

#include <vector>
#include <string>

using namespace std;

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
    int index = (ruleKey == "type") ? 0 : (ruleKey == "color") ? 1 : 2;
    int count = 0;
    for (auto& item : items) {
        if (item[index] == ruleValue) {
            count++;
        }
    }
    return count;
}

JavaScript

function countMatches(items, ruleKey, ruleValue) {
    const index = ruleKey === 'type' ? 0 : ruleKey === 'color' ? 1 : 2;
    let count = 0;
    for (const item of items) {
        if (item[index] === ruleValue) {
            count++;
        }
    }
    return count;
}

const items = [["phone", "blue", "pixel"],["computer", "silver", "lenovo"],["phone", "gold", "iphone"]];
const ruleKey = "color";
const ruleValue = "silver";
console.log(countMatches(items, ruleKey, ruleValue));

#include <stdio.h>
#include <string.h>

int countMatches(char items[][3][11], int itemsSize, char *ruleKey, char *ruleValue) {
    int index = (strcmp(ruleKey, "type") == 0) ? 0 : (strcmp(ruleKey, "color") == 0) ? 1 : 2;
    int count = 0;
    for (int i = 0; i < itemsSize; i++) {
        if (strcmp(items[i][index], ruleValue) == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    char items[3][3][11] = { {"phone", "blue", "pixel"}, {"computer", "silver", "lenovo"}, {"phone", "gold", "iphone"} };
    char ruleKey[] = "color";
    char ruleValue[] = "silver";
    printf("%d\n", countMatches(items, 3, ruleKey, ruleValue));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountMatches(IList<IList<string>> items, string ruleKey, string ruleValue) {
        int index = ruleKey == "type" ? 0 : ruleKey == "color" ? 1 : 2;
        int count = 0;
        foreach (var item in items) {
            if (item[index] == ruleValue) {
                count++;
            }
        }
        return count;
    }

    public static void Main() {
        List<IList<string>> items = new List<IList<string>> {
            new List<string> { "phone", "blue", "pixel" },
            new List<string> { "computer", "silver", "lenovo" },
            new List<string> { "phone", "gold", "iphone" }
        };
        Solution sol = new Solution();
        Console.WriteLine(sol.CountMatches(items, "color", "silver"));
    }
}

This Python solution utilizes list indexing. The index corresponding to the ruleKey is determined using conditional expressions. It loops through each item and checks the attribute specified by the index for equality with the ruleValue, summing the matches.

Complexity

Time Complexity: O(n), where n is the number of items.
Space Complexity: O(1), as it uses constant space relative to input size.

Try this approach in the editor

Approach 2: Direct Attribute Matching

This approach directly checks each item attribute against the ruleValue based on the ruleKey. We manage this by case-selecting the property to compare without indexing.

Python

def countMatches(items, ruleKey, ruleValue):
    count = 0
    for item in items:
        if ((ruleKey == 'type' and item[0] == ruleValue) or
            (ruleKey == 'color' and item[1] == ruleValue) or
            (ruleKey == 'name' and item[2] == ruleValue)):
            count += 1
    return count

items = [["phone","blue","pixel"],["computer","silver","lenovo"],["phone","gold","iphone"]]
ruleKey = "color"
ruleValue = "silver"
print(countMatches(items, ruleKey, ruleValue))

Java

import java.util.List;

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)) ||
                (ruleKey.equals("color") && item.get(1).equals(ruleValue)) ||
                (ruleKey.equals("name") && item.get(2).equals(ruleValue))) {
                count++;
            }
        }
        return count;
    }
}

C++

#include <vector>
#include <string>

using namespace std;

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
    int count = 0;
    for (auto& item : items) {
        if ((ruleKey == "type" && item[0] == ruleValue) ||
            (ruleKey == "color" && item[1] == ruleValue) ||
            (ruleKey == "name" && item[2] == ruleValue)) {
            count++;
        }
    }
    return count;
}

JavaScript

function countMatches(items, ruleKey, ruleValue) {
    let count = 0;
    for (const item of items) {
        if ((ruleKey === 'type' && item[0] === ruleValue) ||
            (ruleKey === 'color' && item[1] === ruleValue) ||
            (ruleKey === 'name' && item[2] === ruleValue)) {
            count++;
        }
    }
    return count;
}

const items = [["phone", "blue", "pixel"],["computer", "silver", "lenovo"],["phone", "gold", "iphone"]];
const ruleKey = "color";
const ruleValue = "silver";
console.log(countMatches(items, ruleKey, ruleValue));

#include <stdio.h>
#include <string.h>

int countMatches(char items[][3][11], int itemsSize, char *ruleKey, char *ruleValue) {
    int count = 0;
    for (int i = 0; i < itemsSize; i++) {
        if ((strcmp(ruleKey, "type") == 0 && strcmp(items[i][0], ruleValue) == 0) ||
            (strcmp(ruleKey, "color") == 0 && strcmp(items[i][1], ruleValue) == 0) ||
            (strcmp(ruleKey, "name") == 0 && strcmp(items[i][2], ruleValue) == 0)) {
            count++;
        }
    }
    return count;
}

int main() {
    char items[3][3][11] = { {"phone", "blue", "pixel"}, {"computer", "silver", "lenovo"}, {"phone", "gold", "iphone"} };
    char ruleKey[] = "color";
    char ruleValue[] = "silver";
    printf("%d\n", countMatches(items, 3, ruleKey, ruleValue));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountMatches(IList<IList<string>> items, string ruleKey, string ruleValue) {
        int count = 0;
        foreach (var item in items) {
            if ((ruleKey == "type" && item[0] == ruleValue) ||
                (ruleKey == "color" && item[1] == ruleValue) ||
                (ruleKey == "name" && item[2] == ruleValue)) {
                count++;
            }
        }
        return count;
    }

    public static void Main() {
        List<IList<string>> items = new List<IList<string>> {
            new List<string> { "phone", "blue", "pixel" },
            new List<string> { "computer", "silver", "lenovo" },
            new List<string> { "phone", "gold", "iphone" }
        };
        Solution sol = new Solution();
        Console.WriteLine(sol.CountMatches(items, "color", "silver"));
    }
}

In Python, the function evaluates each possible ruleKey directly against the respective element of each item, based on conditions set in the if-statement.

Complexity

Time Complexity: O(n), for n items processed.
Space Complexity: O(1), constant space usage.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function countMatches(items: string[][], ruleKey: string, ruleValue: string): number {
    const key = ruleKey === 'type' ? 0 : ruleKey === 'color' ? 1 : 2;
    return items.reduce((r, v) => r + (v[key] === ruleValue ? 1 : 0), 0);
}

func countMatches(items [][]string, ruleKey string, ruleValue string) (ans int) {
	i := map[byte]int{'t': 0, 'c': 1, 'n': 2}[ruleKey[0]]
	for _, v := range items {
		if v[i] == ruleValue {
			ans++
		}
	}
	return
}

Rust

impl Solution {
    pub fn count_matches(items: Vec<Vec<String>>, rule_key: String, rule_value: String) -> i32 {
        let key = if rule_key == "type" {
            0
        } else if rule_key == "color" {
            1
        } else {
            2
        };
        items.iter().filter(|v| v[key] == rule_value).count() as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Index Mapping Method	Time Complexity: O(n), where n is the number of items. Space Complexity: O(1), as it uses constant space relative to input size.
Direct Attribute Matching	Time Complexity: O(n), for n items processed. Space Complexity: O(1), constant space usage.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Index Mapping Method	O(n)	O(1)	Best general approach when attribute positions are fixed and you want cleaner loop logic
Direct Attribute Matching	O(n)	O(1)	Simple implementation when there are only a few attributes and readability is preferred

Frequently asked questions

Is Count Items Matching a Rule easy or hard?

Count Items Matching a Rule is classified as Easy on LeetCode with a high acceptance rate above 80%. The problem mainly tests basic array traversal, string comparison, and conditional logic.

Count Items Matching a Rule Python/Java solution

Both Python and Java implementations follow the same idea: determine the index for the ruleKey, iterate through the items list, and count matches. The algorithm uses a simple loop and string equality check, giving O(n) time and O(1) space complexity.

How to solve Count Items Matching a Rule in O(n)?

Map the ruleKey to its attribute index: type → 0, color → 1, name → 2. Iterate through each item and check if items[i][index] equals ruleValue. Increment a counter whenever the condition is true. The single pass over the array ensures O(n) time complexity.

What is the best approach for Count Items Matching a Rule?

The index mapping method is the cleanest approach. Convert the ruleKey (type, color, or name) into its corresponding index in the item array, then iterate once through the list and compare values. This runs in O(n) time with O(1) extra space and keeps the loop logic simple.

Is Count Items Matching a Rule asked at Google/Amazon/Meta?

This problem is an entry-level array and string filtering question commonly used in screening rounds or practice sets. Variants of attribute filtering appear in interviews at companies like Amazon and Google to test iteration, indexing, and conditional logic.

What data structure is used in Count Items Matching a Rule?

The core data structure is a 2D array (or list of lists) containing string attributes. The solution mainly uses array traversal and string comparison. No additional structures like hash maps are required for the optimal approach.

What is the time complexity of Count Items Matching a Rule?

The optimal solution runs in O(n) time because the algorithm scans the list of items exactly once. Each comparison is constant time. Space complexity is O(1) since only a counter and a few variables are used.

Count Items Matching a Rule solution and explanation

The problem

Approach overview

Approach 1: Index Mapping Method

Approach 2: Direct Attribute Matching

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Items Matching a Rule solution and explanation

The problem

Approach overview

Approach 1: Index Mapping Method

Approach 2: Direct Attribute Matching

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems