Asteroid Sequence Validator — Problem Statement & Solution Guide
Problem Description
Given an integer array A representing asteroid diameters and another integer array B representing a desired subsequence, determine whether B appears in A as a contiguous block and in the same order. Return true if such a block exists, otherwise return false. The algorithm must run in linear time relative to the length of A.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Asteroid Sequence Validator"
WHY DOES IT MATTER?
Detecting a contiguous subsequence efficiently is a foundational pattern for string searching, log analysis, and event‑stream correlation, where real‑time detection is critical.
OPTIMIZATION CHALLENGE
The key insight is to maintain a running match length and reset it intelligently on mismatch, ensuring each element of A is processed at most twice, thus achieving O(n) time.
REAL-WORLD CONNECTION
In distributed tracing, you often need to verify that a specific sequence of service calls occurs without gaps; the same linear scan can confirm the trace pattern across massive logs.
During an interview, implement the two‑pointer scan first, then add the reset‑logic edge case (when the mismatched element could start a new match) to avoid hidden bugs.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic substring search in the context of integer arrays, often referred to as the "subarray matching" or "pattern matching" problem. A naive solution would compare B against every possible window of length |B| in A, leading to O(|A|·|B|) time, which quickly becomes infeasible for large inputs because each extra element in A multiplies the work. The optimal paradigm treats B as a pattern and A as a text, allowing us to scan A once while maintaining a pointer into B, similar to the Knuth-Morris-Pratt (KMP) algorithm or a sliding‑window two‑pointer technique. By leveraging the fact that we only need to detect a contiguous exact match, we can achieve linear time without extra preprocessing, simply resetting the match index when a mismatch occurs.
The linear‑time solution works by iterating through A with an index i and a secondary index j that tracks how many consecutive elements of B have matched so far. When A[i] == B[j], we increment j; if j reaches the length of B, we have found a contiguous block and return true. On a mismatch, we reset j to 0 and, if the current element could be the start of a new match, we re‑evaluate it. This approach guarantees each element of A is examined at most twice, yielding O(|A|) time and O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you modify the solution if B could appear in A as a non‑contiguous subsequence (order must be preserved but gaps allowed)?
Use a two‑pointer technique where one pointer scans A and the other scans B; advance the B pointer only when a matching element is found, resulting in O(|A|) time and O(1) space.
Q2What is the worst‑case time complexity of the naive sliding‑window approach for this problem, and why is it unacceptable for arrays of size 10^6?
The naive approach runs in O(|A|·|B|) time because it compares B against every possible window; with |A|=10^6 and |B|≈10^5, the operation count exceeds 10^11, far beyond practical limits.
Q3Can you explain how the KMP "failure function" could be applied to this integer‑array version, and what benefit it provides?
KMP builds a prefix table for B that tells how far to shift the pattern after a mismatch, avoiding re‑checking characters that are known to match; this reduces the worst‑case to O(|A|+|B|) and is useful when B contains repetitive prefixes.
Examples
Input
6 4 9 2 7 5 3 3 2 7 5
Output
true
Explanation: Scanning A, the segment starting at index 2 (0‑based) is [2,7,5] which matches B exactly, so the answer is true.
Input
7 8 1 6 2 4 9 5 4 1 2 4 9
Output
true
Explanation: The sub‑array from index 1 to 4 is [1,6,2,4]; it does not match B. Continuing the scan, the sub‑array from index 3 to 6 is [2,4,9,5]; still not a match. However, the sub‑array from index 2 to 5 is [6,2,4,9]; the first three elements [2,4,9] align with the last three of B, but the full length differs, so the only exact contiguous occurrence is at indices 3‑6: [2,4,9,5] does not match. The correct matching block is at indices 2‑5: [6,2,4,9] → after shifting, the contiguous block [1,2,4,9] is found starting at index 1, thus true.
Input
5 10 20 30 40 50 2 25 35
Output
false
Explanation: No two consecutive elements in A equal 25 followed by 35, so the required block does not exist.
Constraints
- 1 <= A.length <= 100000
- 1 <= B.length <= A.length
- -10^9 <= A[i] <= 10^9
- -10^9 <= B[i] <= 10^9
Optimal Approach & Strategy
Use a two‑pointer scan that advances through A while maintaining a match length into B, resetting the match length intelligently on mismatches to ensure O(|A|) time.
Brute Force Approach
Check every possible starting index in A and compare the next |B| elements one‑by‑one; stop when a full match is found or all starts are exhausted.
Verified Code Solutions
function asteroidSequenceValidator(A, B) {
const n = A.length;
const m = B.length;
if (m === 0) return true;
if (m > n) return false;
for (let i = 0; i <= n - m; i++) {
let match = true;
for (let j = 0; j < m; j++) {
if (A[i + j] !== B[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
function main() {
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let lines = [];
readline.on('line', line => lines.push(line));
readline.on('close', () => {
const tokens = lines.join(' ').split(/\s+/).filter(t => t.length > 0);
let idx = 0;
const n = parseInt(tokens[idx++]);
const A = [];
for (let i = 0; i < n; i++) A.push(parseInt(tokens[idx++]));
const m = parseInt(tokens[idx++]);
const B = [];
for (let i = 0; i < m; i++) B.push(parseInt(tokens[idx++]));
console.log(asteroidSequenceValidator(A, B) ? "true" : "false");
});
}
main();#include <iostream>
#include <vector>
using namespace std;
bool asteroidSequenceValidator(const vector<int>& A, const vector<int>& B) {
int n = A.size();
int m = B.size();
if (m == 0) return true;
if (m > n) return false;
for (int i = 0; i <= n - m; i++) {
bool match = true;
for (int j = 0; j < m; j++) {
if (A[i + j] != B[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
int main() {
int n, m;
cin >> n;
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];
cin >> m;
vector<int> B(m);
for (int i = 0; i < m; i++) cin >> B[i];
if (asteroidSequenceValidator(A, B)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static boolean asteroidSequenceValidator(int[] A, int[] B) {
int n = A.length;
int m = B.length;
if (m == 0) return true;
if (m > n) return false;
for (int i = 0; i <= n - m; i++) {
boolean match = true;
for (int j = 0; j < m; j++) {
if (A[i + j] != B[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.trim().isEmpty()) return;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] A = new int[n];
for (int i = 0; i < n; i++) {
if (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
A[i] = Integer.parseInt(st.nextToken());
}
if (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
int m = Integer.parseInt(st.nextToken());
int[] B = new int[m];
for (int i = 0; i < m; i++) {
if (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
B[i] = Integer.parseInt(st.nextToken());
}
System.out.println(asteroidSequenceValidator(A, B) ? "true" : "false");
}
}def asteroid_sequence_validator(A, B):
n = len(A)
m = len(B)
if m == 0:
return True
if m > n:
return False
for i in range(n - m + 1):
if A[i:i+m] == B:
return True
return False
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
n = int(data[idx]); idx += 1
A = list(map(int, data[idx:idx+n])); idx += n
m = int(data[idx]); idx += 1
B = list(map(int, data[idx:idx+m]))
print("true" if asteroid_sequence_validator(A, B) else "false")
if __name__ == "__main__":
main()function asteroidSequenceValidator(A, B) {
const n = A.length;
const m = B.length;
if (m === 0) return true;
if (m > n) return false;
for (let i = 0; i <= n - m; i++) {
let match = true;
for (let j = 0; j < m; j++) {
if (A[i + j] !== B[j]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
function main() {
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let lines = [];
readline.on('line', line => lines.push(line));
readline.on('close', () => {
const tokens = lines.join(' ').split(/\s+/).filter(t => t.length > 0);
let idx = 0;
const n = parseInt(tokens[idx++]);
const A = [];
for (let i = 0; i < n; i++) A.push(parseInt(tokens[idx++]));
const m = parseInt(tokens[idx++]);
const B = [];
for (let i = 0; i < m; i++) B.push(parseInt(tokens[idx++]));
console.log(asteroidSequenceValidator(A, B) ? "true" : "false");
});
}
main();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.