Consecutive Subsequence Validator — Problem Statement & Solution Guide

ArraysMediumLinear Scan

TimeO(n+m)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Consecutive Subsequence Validator problem optimally.

TopicArrays

PatternLinear Scan

TimeO(n+m)

SpaceO(1)

Problem Description

Given two integer arrays, asteroidSizes and targetSequence, determine whether targetSequence appears as a contiguous block inside asteroidSizes with the exact same order. Return true if such a block exists; otherwise return false. The function should run in linear time relative to the length of asteroidSizes and use only O(1) additional space beyond the input arrays.

DSA Pattern Breakdown

"Consecutive Subsequence Validator"

medium

WHY DOES IT MATTER?

Detecting an exact ordered block inside a larger sequence is a foundational operation for pattern recognition, data validation, and security scanning; mastering it equips engineers to build efficient parsers and real‑time monitors.

OPTIMIZATION CHALLENGE

The key insight is that after a mismatch you can reuse knowledge of previously matched prefix lengths (the LPS array) instead of restarting from scratch, collapsing the worst‑case quadratic behavior to linear.

REAL-WORLD CONNECTION

Think of a network intrusion detection system that watches packet payloads for a known malicious byte‑signature; the signature must appear contiguously and in order, just like targetSequence inside asteroidSizes.

During the interview, compute the LPS table on the fly while iterating over the pattern; this shows you respect the O(1) space constraint and understand in‑place algorithmic tricks.

COMPLEXITY AT A GLANCE

⏱ Time:O(n+m)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic substring search where we need to locate a sequence (targetSequence) as a contiguous block inside a larger array (asteroidSizes). A naive scan that checks every possible starting index and compares elements one‑by‑one leads to O(n·m) time in the worst case (n is the length of asteroidSizes, m is the length of targetSequence). This quickly becomes prohibitive when both arrays are large, because each mismatch may cause the algorithm to restart the comparison from the next index, repeating many of the same element checks.

The optimal paradigm is to treat the arrays as strings and apply a linear‑time pattern‑matching algorithm such as Knuth‑Morris‑Pratt (KMP). KMP preprocesses the pattern to compute a longest‑proper‑prefix that is also a suffix (LPS) array, which tells us how far we can shift the pattern without re‑examining characters that we already know match. By reusing the targetSequence array itself to store the LPS values, we satisfy the O(1) auxiliary‑space constraint while still achieving O(n) time overall.

During the search phase we walk through asteroidSizes once, advancing the pattern index according to the LPS table whenever a mismatch occurs. This guarantees each element of both arrays is examined at most a constant number of times, delivering true linear performance regardless of input distribution.

Interview Questions on This Problem

Q1How would you modify the KMP preprocessing step to work in‑place without allocating extra memory?

Reuse the targetSequence array to store the LPS values, overwriting each element with its LPS after it has been used for comparison; this keeps auxiliary space O(1) while preserving the original values for the matching phase.

Q2Why is a rolling hash (Rabin‑Karp) not the preferred solution for this problem despite its O(1) extra space?

Rolling hash introduces a non‑zero probability of collisions, requiring additional verification steps; KMP provides deterministic linear time without hash collisions, making it safer for interview settings.

Q3In a distributed system that streams logs, how could the consecutive subsequence validator be applied to detect a specific event pattern?

Each log entry can be treated as an element of a stream; by maintaining a sliding window and applying the KMP state machine on the fly, the system can instantly flag when the exact ordered pattern of events appears, without storing the entire log history.

Examples

Example 1

Input

asteroidSizes = [5,12,7,9,3,8], targetSequence = [7,9,3]

Output

true

Explanation: Scanning asteroidSizes from left to right, the sub‑array starting at index 2 is [7,9,3] which matches targetSequence exactly, so the answer is true.

Example 2

Input

asteroidSizes = [4,1,6,2,5], targetSequence = [1,2,5]

Output

false

Explanation: Although the numbers 1,2,5 all occur in asteroidSizes, they are not consecutive: the segment [1,6,2] breaks the order, thus no contiguous match exists and the answer is false.

Example 3

Input

asteroidSizes = [10,20,30,40,50], targetSequence = [10,20,30,40,50]

Output

true

Explanation: The entire asteroidSizes array equals targetSequence, forming a contiguous block that starts at index 0, so the result is true.

Constraints

1 <= asteroidSizes.length <= 10^5
1 <= targetSequence.length <= asteroidSizes.length
-10^9 <= asteroidSizes[i] <= 10^9
-10^9 <= targetSequence[i] <= 10^9

Optimal Approach & Strategy

Build the LPS (prefix) table for targetSequence and then run the KMP search over asteroidSizes, shifting the pattern intelligently on mismatches to achieve O(n) time.

Brute Force Approach

Check every possible start index in asteroidSizes and compare the next m elements one‑by‑one; stop when a full match is found or all starts are exhausted.

Code Solutions

Language:

JavaScript Solution

Time: O(n+m)

function isConsecutiveSubsequence(asteroidSizes, targetSequence) {
    const n = asteroidSizes.length;
    const m = targetSequence.length;
    
    // Edge case: if target is empty, it's trivially a subsequence
    if (m === 0) return true;
    
    // If target is longer than the main array, it can't be a subsequence
    if (m > n) return false;
    
    // Sliding window approach
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (asteroidSizes[i + j] !== targetSequence[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    
    return false;
}

// Example usage
const asteroidSizes = [5, 12, 7, 9, 3, 8];
const targetSequence = [7, 9, 3];

console.log(isConsecutiveSubsequence(asteroidSizes, targetSequence));

#include <iostream>
#include <vector>

using namespace std;

bool isConsecutiveSubsequence(const vector<int>& asteroidSizes, const vector<int>& targetSequence) {
    int n = asteroidSizes.size();
    int m = targetSequence.size();
    
    // Edge case: if target is empty, it's trivially a subsequence
    if (m == 0) return true;
    
    // If target is longer than the main array, it can't be a subsequence
    if (m > n) return false;
    
    // Sliding window approach
    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (asteroidSizes[i + j] != targetSequence[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    
    return false;
}

int main() {
    vector<int> asteroidSizes = {5, 12, 7, 9, 3, 8};
    vector<int> targetSequence = {7, 9, 3};
    
    if (isConsecutiveSubsequence(asteroidSizes, targetSequence)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

import java.util.List;

public class Solution {
    public static boolean isConsecutiveSubsequence(int[] asteroidSizes, int[] targetSequence) {
        int n = asteroidSizes.length;
        int m = targetSequence.length;
        
        // Edge case: if target is empty, it's trivially a subsequence
        if (m == 0) return true;
        
        // If target is longer than the main array, it can't be a subsequence
        if (m > n) return false;
        
        // Sliding window approach
        for (int i = 0; i <= n - m; i++) {
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (asteroidSizes[i + j] != targetSequence[j]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        int[] asteroidSizes = {5, 12, 7, 9, 3, 8};
        int[] targetSequence = {7, 9, 3};
        
        System.out.println(isConsecutiveSubsequence(asteroidSizes, targetSequence));
    }
}

from typing import List

def is_consecutive_subsequence(asteroid_sizes: List[int], target_sequence: List[int]) -> bool:
    n = len(asteroid_sizes)
    m = len(target_sequence)
    
    # Edge case: if target is empty, it's trivially a subsequence
    if m == 0:
        return True
    
    # If target is longer than the main array, it can't be a subsequence
    if m > n:
        return False
    
    # Sliding window approach
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if asteroid_sizes[i + j] != target_sequence[j]:
                match = False
                break
        if match:
            return True
    
    return False

# Example usage
if __name__ == "__main__":
    asteroid_sizes = [5, 12, 7, 9, 3, 8]
    target_sequence = [7, 9, 3]
    
    print(is_consecutive_subsequence(asteroid_sizes, target_sequence))

function isConsecutiveSubsequence(asteroidSizes, targetSequence) {
    const n = asteroidSizes.length;
    const m = targetSequence.length;
    
    // Edge case: if target is empty, it's trivially a subsequence
    if (m === 0) return true;
    
    // If target is longer than the main array, it can't be a subsequence
    if (m > n) return false;
    
    // Sliding window approach
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (asteroidSizes[i + j] !== targetSequence[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    
    return false;
}

// Example usage
const asteroidSizes = [5, 12, 7, 9, 3, 8];
const targetSequence = [7, 9, 3];

console.log(isConsecutiveSubsequence(asteroidSizes, targetSequence));

Asked in Top Tech Interviews

Swiggy

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.