Count Items Matching a Rule
EasyPrompt
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 ith item is said to match the rule if one of the following is true:
ruleKey == "type"andruleValue == typei.ruleKey == "color"andruleValue == colori.ruleKey == "name"andruleValue == namei.
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 <= 1041 <= typei.length, colori.length, namei.length, ruleValue.length <= 10ruleKeyis equal to either"type","color", or"name".- All strings consist only of lowercase letters.
Approaches
3 approaches with complexity analysis and trade-offs.
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
itemin theitemslist. - Inside the loop, use a series of
if-else ifstatements to check the value ofruleKey:- If
ruleKeyis "type", compareitem.get(0)withruleValue. If they match, incrementmatchCount. - If
ruleKeyis "color", compareitem.get(1)withruleValue. If they match, incrementmatchCount. - If
ruleKeyis "name", compareitem.get(2)withruleValue. If they match, incrementmatchCount.
- If
- After the loop finishes, return
matchCount.
Walkthrough
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
Time
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
O(1), as we only use a constant amount of extra space for the counter variable.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra data structures.
Cons
Repeats the
ruleKeystring comparison in every iteration of the loop, which is slightly inefficient, though the performance impact is negligible in practice.
This approach leverages Java 8 Streams to provide a more concise and declarative solution. It performs the same logic as the iterative approaches but expresses it in a functional style, which can lead to cleaner and more readable code.
Algorithm
- First, determine the index corresponding to the
ruleKey. Aswitchstatement is a clean way to do this. - Create a stream from the
itemslist usingitems.stream(). - Use the
filter()intermediate operation. The predicate for the filter will check if an item's attribute at the determined index matches theruleValue. - Use the
count()terminal operation to count the number of items that passed the filter. - Cast the resulting
longto anintand return it.
Walkthrough
Instead of an explicit loop, we can use the Stream API. First, we determine the index to check based on the ruleKey, just like in the optimized iterative approach. Then, we convert the items list into a stream. We apply a filter operation to the stream, keeping only the items where the value at the determined index matches the ruleValue. Finally, we use the count terminal operation to get the number of elements remaining in the stream.
import java.util.List; class Solution { public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) { int index; switch (ruleKey) { case "type": index = 0; break; case "color": index = 1; break; default: // "name" index = 2; break; } return (int) items.stream() .filter(item -> item.get(index).equals(ruleValue)) .count(); }}Complexity
Time
O(N), where N is the number of items. The stream processes each item once to filter and count.
Space
O(1). Although streams can sometimes use more memory, for a simple filter-count operation, the space usage is minimal and effectively constant.
Trade-offs
Pros
Very concise and readable, especially for those familiar with functional programming.
Clearly expresses the intent of filtering and counting.
Cons
Can have a slight performance overhead compared to a simple for-loop in some Java versions or scenarios.
Might be less intuitive for developers not familiar with functional programming concepts.
This approach improves upon the brute-force method by first determining the index that corresponds to the ruleKey. This avoids redundant string comparisons inside the main loop, making the code slightly cleaner and more efficient. This is generally the most performant and clear way to solve the problem.
Algorithm
- First, determine the index to check based on
ruleKey. Create a variable,ruleIndex. - Use an
if-else ifblock or aswitchstatement onruleKeyto setruleIndex: 0 for "type", 1 for "color", and 2 for "name". - Initialize a counter variable,
matchCount, to zero. - Loop through every
itemin theitemslist. - Inside the loop, directly access the element at
item.get(ruleIndex)and compare it withruleValue. - If they match, increment
matchCount. - After the loop, return
matchCount.
Walkthrough
The key optimization here is to avoid re-evaluating the ruleKey string in every iteration of the loop. We can determine which index (0 for type, 1 for color, 2 for name) we need to check just once before the loop begins. Then, inside the loop, we can use this pre-calculated index to directly access the correct property of each item for comparison. This separation of concerns makes the code cleaner and avoids a small amount of redundant work.
class Solution { public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) { int ruleIndex; if (ruleKey.equals("type")) { ruleIndex = 0; } else if (ruleKey.equals("color")) { ruleIndex = 1; } else { // ruleKey is "name" ruleIndex = 2; } int count = 0; for (List<String> item : items) { if (item.get(ruleIndex).equals(ruleValue)) { count++; } } return count; }}Complexity
Time
O(N), where N is the number of items. We perform one check to determine the index and then iterate through all N items once.
Space
O(1), as we only use a constant amount of extra space for the counter and the index variable.
Trade-offs
Pros
Most efficient iterative solution as it avoids repeated string comparisons of
ruleKeyinside the loop.The logic is very clear, with index determination separated from the counting loop.
Cons
No significant cons, as this is an optimal solution for the given problem constraints.
Solutions
Solution
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; }}class Solution {public: int countMatches(vector<vector<string>> &items, string ruleKey, string ruleValue) { int i = ruleKey[0] == 't' ? 0 : (ruleKey[0] == 'c' ? 1 : 2); return count_if(items.begin(), items.end(), [&](auto &v) { return v[i] == ruleValue; }); }};class Solution: def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int: i = 0 if ruleKey[0] == 't' else (1 if ruleKey[0] == 'c' else 2) return sum(v[i] == ruleValue for v in items)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.