Validate Nested Signal Pairs — Problem Statement & Solution Guide

StackMediumMixed

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Stack and solve the Validate Nested Signal Pairs problem optimally.

TopicStack

PatternMixed

TimeO(n)

SpaceO(n)

Problem Description

Given an array of strings representing a sequence of signals, each element is either an opening signal formatted as "openX" or a closing signal formatted as "closeX", where X denotes the signal type (a non‑empty alphabetic identifier). Determine whether the sequence is valid: every opening signal must be matched by a later closing signal of the same type, and the matched pairs must be properly nested (i.e., the most recent unmatched opening signal must be closed first). Return true if the sequence satisfies these conditions; otherwise, return false.

DSA Pattern Breakdown

"Validate Nested Signal Pairs"

medium

WHY DOES IT MATTER?

Proper nesting validation appears in compilers, markup parsers, protocol handshakes, and any system that requires balanced start‑end semantics; mastering the stack pattern prevents subtle bugs that cascade into security or data‑integrity issues.

OPTIMIZATION CHALLENGE

The insight is that each token only needs to be examined once; by using a stack we avoid repeated scans for matching pairs, collapsing a potential quadratic process into linear time.

REAL-WORLD CONNECTION

Think of a call stack in a distributed tracing system: each service call (open) must return (close) before the caller proceeds, mirroring the push‑pop discipline of a stack.

When coding, push the identifier together with its index; this tiny addition lets you report precise error locations without extra passes, a trick interviewers love to see.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The validation of nested signal pairs is a classic instance of the matching‑parentheses problem, generalized to multiple token types. A stack provides a natural LIFO structure: every time an "openX" token appears we push its identifier X onto the stack, and when a "closeX" token appears we check that the stack’s top matches X before popping. This guarantees that the most recent unmatched opening signal is closed first, preserving proper nesting. A naïve solution might scan the array for each opening token and search forward for its matching closing token, leading to O(n²) time in the worst case and failing on large inputs because each search repeats work already done; it also struggles to detect interleaved mismatches. The optimal paradigm leverages a single pass with a stack, achieving linear time and constant‑amortized extra space per element, because each element is pushed and popped at most once.

Interview Questions on This Problem

Q1How would you modify the stack‑based solution to also return the index of the first mismatched closing signal, if any?

While processing, keep track of the current index; when a closing token does not match the stack top (or the stack is empty), immediately return that index as the error position. If the loop finishes with a non‑empty stack, the first unmatched opening’s index (stored alongside the identifier) is the error.

Q2At a fintech firm you need to validate a stream of transaction start/stop events (e.g., "startDeposit"/"stopDeposit"). How does the nested‑signal algorithm help, and what extra constraints might you need to enforce?

The algorithm ensures every start event is closed in the correct order, preventing overlapping deposits. Additional constraints could include time‑window limits, idempotent handling of duplicate stops, or limiting the depth of nesting for regulatory reasons, which can be checked alongside the stack operations.

Q3A high‑growth startup wants to parallelize validation of a massive log file split across shards. What challenges arise and how would you design a solution?

Parallel shards break the global nesting order, so each shard can be processed locally to produce a summary: a stack of unmatched opens and a list of unmatched closes. A reduction step merges these summaries by matching the tail of one shard’s opens with the head of the next shard’s closes, effectively performing a distributed stack reduction in O(k) where k is the number of shards.

Examples

Example 1

Input

["openA","openB","closeB","closeA"]

Output

true

Explanation: "openA" pushes type A onto the stack. "openB" pushes B. "closeB" matches the top of the stack (B) and pops it. "closeA" matches the remaining top (A) and pops it. Stack ends empty → valid.

Example 2

Input

["openA","openB","closeA","closeB"]

Output

false

Explanation: After "openA" and "openB", the stack is [A,B]. "closeA" expects B on top but finds A, causing a mismatch. Hence the sequence is invalid.

Example 3

Input

["openA","closeA","closeA"]

Output

false

Explanation: "openA" pushes A, "closeA" correctly pops it leaving an empty stack. The next "closeA" finds no matching opening signal, so the sequence is invalid.

Constraints

1 <= signals.length <= 100000
Each signal string length is between 5 and 10 characters
Signal type identifier X consists only of uppercase English letters
The array contains only strings that start with "open" or "close

Optimal Approach & Strategy

Traverse once, pushing identifiers on a stack for opens and popping for closes while checking equality – O(n) time and O(n) space in the worst case.

Brute Force Approach

For each opening token, scan forward to find the first matching closing token, marking used tokens; repeat until all are processed – this leads to O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function validateNestedSignalPairs(signals) {
    const stack = [];
    for (const signal of signals) {
        if (signal.startsWith("open")) {
            stack.push(signal);
        } else if (signal.startsWith("close")) {
            if (stack.length === 0) {
                return false;
            }
            const top = stack.pop();
            if (top !== "open" + signal.slice(5)) {
                return false;
            }
        } else {
            return false;
        }
    }
    return stack.length === 0;
}

const signals = ["openA", "openB", "closeB", "closeA"];
console.log(validateNestedSignalPairs(signals));

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

bool validateNestedSignalPairs(vector<string>& signals) {
    stack<string> st;
    for (const string& signal : signals) {
        if (signal.size() > 4 && signal.substr(0, 4) == "open") {
            st.push(signal);
        } else if (signal.size() > 5 && signal.substr(0, 5) == "close") {
            if (st.empty()) {
                return false;
            }
            string top = st.top();
            st.pop();
            if (top != "open" + signal.substr(5)) {
                return false;
            }
        } else {
            return false;
        }
    }
    return st.empty();
}

int main() {
    vector<string> signals = {"openA", "openB", "closeB", "closeA"};
    cout << (validateNestedSignalPairs(signals) ? "true" : "false") << endl;
    return 0;
}

import java.util.List;
import java.util.Stack;

public class Solution {
    public static boolean validateNestedSignalPairs(List<String> signals) {
        Stack<String> stack = new Stack<>();
        for (String signal : signals) {
            if (signal.startsWith("open")) {
                stack.push(signal);
            } else if (signal.startsWith("close")) {
                if (stack.isEmpty()) {
                    return false;
                }
                String top = stack.pop();
                if (!top.equals("open" + signal.substring(5))) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        List<String> signals = List.of("openA", "openB", "closeB", "closeA");
        System.out.println(validateNestedSignalPairs(signals));
    }
}

def validate_nested_signal_pairs(signals):
    stack = []
    for signal in signals:
        if signal.startswith("open"):
            stack.append(signal)
        elif signal.startswith("close"):
            if not stack:
                return False
            top = stack.pop()
            if top != "open" + signal[5:]:
                return False
        else:
            return False
    return len(stack) == 0

if __name__ == "__main__":
    signals = ["openA", "openB", "closeB", "closeA"]
    print(validate_nested_signal_pairs(signals))

function validateNestedSignalPairs(signals) {
    const stack = [];
    for (const signal of signals) {
        if (signal.startsWith("open")) {
            stack.push(signal);
        } else if (signal.startsWith("close")) {
            if (stack.length === 0) {
                return false;
            }
            const top = stack.pop();
            if (top !== "open" + signal.slice(5)) {
                return false;
            }
        } else {
            return false;
        }
    }
    return stack.length === 0;
}

const signals = ["openA", "openB", "closeB", "closeA"];
console.log(validateNestedSignalPairs(signals));

Asked in Top Tech Interviews

RazorpayAmazon

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.