Validate Nested Signal Pairs ā Problem Statement & Solution Guide
Problem Description
Given a sequence of signals represented as a list of strings, implement a function to determine if every opening signal is matched with a corresponding closing signal of the same type, and the signal pairs are properly nested.
Examples
Input
['<a>', '<b>', '</b>', '<a>', '</a>', '</a>', '</b>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>
Output
true
Explanation: Step-by-step: The input sequence starts with an opening signal <a>. The stack is used to keep track of opening signals. When a closing signal </a> is encountered, it is matched with the corresponding opening signal <a> at the top of the stack. This process continues until all signals are processed, resulting in a valid sequence of nested signal pairs.
Input
['<a>', '<b>', '</b>', '<a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>', '</a>
Output
false
Explanation: Step-by-step: The input sequence starts with an opening signal <a>. However, there is no corresponding closing signal </a> to match it, resulting in an invalid sequence of nested signal pairs.
Constraints
- 1 <= sequence length <= 1000
- 0 <= signal frequency <= 10000
Optimal Approach & Strategy
The optimal approach involves using a stack to keep track of the opening signals and their corresponding frequencies, allowing for a time complexity of O(n). This approach is more efficient and scalable for large input sequences.
Brute Force Approach
A brute-force approach would involve checking every possible pair of opening and closing signals, resulting in a time complexity of O(nĀ²). This approach is inefficient and would not be practical for large input sequences.
Verified Code Solutions
class Solution {
public boolean validateNestedSignalPairs(String[] signals) {
Stack<String> stack = new Stack<>();
Map<String, String> signalPairs = new HashMap<>();
signalPairs.put("<a>", "</a>");
signalPairs.put("<b>", "</b>");
for (String signal : signals) {
if (signalPairs.containsKey(signal)) {
stack.push(signal);
} else if (signalPairs.containsValue(signal)) {
if (stack.isEmpty() || !signalPairs.get(stack.pop()).equals(signal)) {
return false;
}
}
}
return stack.isEmpty();
}
}def validate_nested_signal_pairs(signals):
stack = []
signal_pairs = {'<a>': '</a>', '<b>': '</b>'}
for signal in signals:
if signal in signal_pairs.keys():
stack.append(signal)
elif signal in signal_pairs.values():
if not stack or signal_pairs[stack.pop()] != signal:
return False
return not stack
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.