Check Subarray in Arrays | Dataford Interview Questions

The Wells Fargo Mobile app may analyze ordered transaction-event sequences. Given a main array and a candidate array, determine whether the candidate occurs as a contiguous subarray of the main array.

A candidate is a subarray only when its elements appear consecutively and in the same order. Return True if it occurs, and False otherwise. An empty candidate array is considered a subarray of every array.

Formal Specification

Implement is_subarray(main, candidate).

Input: Two integer arrays, main and candidate.
Output: A Boolean indicating whether candidate appears contiguously within main.
Aim for an O(n + m) solution, where n is the length of main and m is the length of candidate.

Constraints

0 <= len(main) <= 100,000
0 <= len(candidate) <= 10,000
-10^9 <= main[i], candidate[i] <= 10^9
The candidate must match in the same order and without gaps

Function Signature

def is_subarray(main, candidate):

Your question is Check Subarray in Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem