Skip to main content
Talentd

Form Array by Concatenating Subarrays of Another Array - Solution & Explanation

MediumArrayTwo PointersGreedyString Matching14 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the ith subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)th subarray appears before the ith subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

 

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
Output: true
Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].
These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
Output: false
Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.
[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
Output: false
Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.
They share a common elements nums[4] (0-indexed).

 

Constraints:

  • groups.length == n
  • 1 <= n <= 103
  • 1 <= groups[i].length, sum(groups[i].length) <= 103
  • 1 <= nums.length <= 103
  • -107 <= groups[i][j], nums[k] <= 107

Approach Overview

Problem Overview: You are given a list of integer subarrays called groups and a main array nums. The task is to determine whether you can form the sequence of groups by concatenating them in order using subarrays from nums. Each group must appear exactly in order and cannot overlap with another matched group.

Approach 1: Greedy Matching Approach (O(n * k) time, O(1) space)

This approach scans nums from left to right and greedily tries to match each group in order. For the current group, compare its elements with the current segment in nums. If all elements match sequentially, move the pointer forward by the length of the group and start matching the next group. If the match fails, advance the pointer in nums by one and try again. The key insight is that once a group matches, skipping exactly its length prevents overlap and preserves order.

The algorithm performs repeated sequential comparisons similar to string matching. Although each attempt compares multiple elements, the pointer only moves forward, so the scan remains efficient. This method relies on simple iteration over the array and works well for interview scenarios because it is straightforward and easy to reason about.

Approach 2: Two Pointer Approach (O(n * k) time, O(1) space)

The two pointer strategy maintains one pointer for nums and another for the current group. As you iterate through nums, check whether the current value matches the first element of the active group. If it does, advance both pointers and continue verifying the rest of that group. If any mismatch occurs, reset the group pointer and continue scanning the main array.

This technique uses the classic two pointers pattern to synchronize traversal between the main array and the current group. Once an entire group matches, increment the group index and continue scanning from the next position in nums. Because groups must appear in order and cannot overlap, pointer movement naturally enforces the constraint.

Recommended for interviews: The greedy matching solution is typically expected. It clearly demonstrates your understanding of sequential matching and pointer control while keeping the implementation simple. A brute-force mindset helps initially, but the greedy scan shows stronger algorithmic clarity and avoids unnecessary backtracking.

Approach 1: Greedy Matching Approach

This approach involves a greedy search through the `nums` array to find each subarray from `groups` in sequence. Starting from the first position, for each subarray in `groups`, check if it aligns with the current sequence in `nums`. If it does, move the index forward by the length of the current subarray in `nums`, ensuring no overlaps or reuse of elements.

This solution uses `memcmp` to compare slices between the current position in `nums` and the target group. If a match is found, it increments the position by the length of the group's slice to ensure the subarrays are disjoint. This process is repeated for each group.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Two Pointer Approach

The two-pointer approach employs two indices to track positions within the `nums` and `groups` arrays. As the main pointer iterates through `nums`, the second pointer verifies each subarray in `groups`. When a full subarray match is identified, the main pointer advances to bypass these elements, ensuring subarrays remain disjoint and ordered.

The C solution employs a helper function `validGroup` to verify subarray matches using a nested loop structure. The code advances only upon valid complete matches.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Matching Approach

Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)

Two Pointer Approach

Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy MatchingO(n * k)O(1)Best general solution. Simple sequential scan with minimal memory.
Two PointerO(n * k)O(1)Useful when explicitly tracking positions in both arrays during matching.

Video Solution

LeetCode 1764. Form Array by Concatenating Subarrays of Another Array | BiWeekly Contest 228 | C++ • Cherry Coding [IIT-G] • 659 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Form Array by Concatenating Subarrays of Another Array easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 54%. The difficulty comes from correctly handling sequential matching and avoiding overlap between groups. Once the greedy scanning idea is clear, the implementation becomes relatively straightforward.
Form Array by Concatenating Subarrays of Another Array Python/Java solution
Most implementations follow the same greedy structure across languages. Iterate through nums, check whether the current position matches the start of the next group, and verify all elements of that group. If they match, advance the pointer by the group length. This logic translates directly into Python, Java, C++, and JavaScript with similar complexity.
How to solve Form Array by Concatenating Subarrays of Another Array in O(n)?
A near-linear scan is achieved using a greedy pointer technique. Iterate through nums and try to match the current group starting at each position. When the full group matches, move the pointer forward by the group's length and switch to the next group. Because the pointer never moves backward, the overall scan behaves close to O(n) in practice.
What is the best approach for Form Array by Concatenating Subarrays of Another Array?
The greedy matching approach is the most common solution. Scan the main array and attempt to match each group sequentially. If a group matches completely, skip ahead by its length and start matching the next group. This method runs in O(n * k) time and O(1) space, where n is the size of nums and k is the maximum group length.
Is Form Array by Concatenating Subarrays of Another Array asked at Google/Amazon/Meta?
Problems involving sequential matching and greedy array traversal appear frequently in interviews at companies like Amazon and Google. Variations of subarray matching, string-style comparisons, and pointer-based scanning are common technical interview topics.
What data structure is used in Form Array by Concatenating Subarrays of Another Array?
The solution primarily uses arrays with pointer-based traversal. No advanced data structures are required. The algorithm relies on sequential comparison, pointer movement, and greedy matching to ensure groups appear in order without overlap.
What is the time complexity of Form Array by Concatenating Subarrays of Another Array?
The typical solution runs in O(n * k) time. The algorithm scans the main array while comparing elements with the current group. In the worst case, each position may attempt a comparison with a group of length k. Space complexity remains O(1) because the algorithm uses only a few pointers.

Ready to solve this problem?

Practice Form Array by Concatenating Subarrays of Another Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays