Form Array by Concatenating Subarrays of Another Array

Form Array by Concatenating Subarrays of Another Array

What is this problem about?

In the Form Array by Concatenating Subarrays of Another Array coding problem, you are given a 2D array groups and a 1D array nums. You need to determine if you can choose non-overlapping subarrays from nums that perfectly match the arrays in groups, in the exact same order. For example, if groups = [[1, 2], [3, 4]], you need to find the sequence [1, 2] in nums, and then after that, find the sequence [3, 4].

Why is this asked in interviews?

Amazon asks this Array interview pattern problem to test your string/array matching skills and your ability to use Greedy algorithms. It evaluates whether you can manage multiple pointers and correctly reset your search state. It's a "Medium" problem that serves as a practical test of implementing a localized search within a larger search space.

Algorithmic pattern used

This problem uses a Greedy and Two Pointers approach.

1. Iterate through the groups array. Let the current group be g.
2. Keep a pointer i for the nums array.
3. Search for g starting from nums[i].
4. If you find g starting at nums[k], move i to k + g.length and proceed to the next group.
5. If you cannot find g in the remaining part of nums, return False. Since we only move forward, picking the first available match for each group is the optimal greedy choice.

Example explanation

groups = [[1, -1, -1], [3, -2, 0]], nums = [1, -1, 0, 1, -1, -1, 3, -2, 0]

1. Look for [1, -1, -1].
   • Index 0: matches [1, -1, 0]? No.
   • Index 3: matches [1, -1, -1]? Yes!
2. Move pointer i to $3 + 3 = 6$.
3. Look for [3, -2, 0] starting from index 6.
   • Index 6: matches [3, -2, 0]? Yes! All groups found. Return True.

Common mistakes candidates make

• Not resetting the inner loop: When trying to match a group, if a mismatch occurs, you must reset the group index but only advance the nums starting index by 1, not by the partial match length.
• Overlapping: Forgetting that once a group is matched, the next group must start strictly after the previous match's end.
• Complex KMP: While KMP can optimize the sub-array search, a simple nested loop is usually sufficient given the constraints and is less prone to bugs during an interview.

Interview preparation tip

Practice writing a clean indexOf(array, subArray, startIndex) helper function. Separating the sub-array matching logic from the main group iteration makes your code much easier to read and debug.