1764. Form Array by Concatenating Subarrays of Another Array LeetCode Solution
In this guide, you will get 1764. Form Array by Concatenating Subarrays of Another Array LeetCode Solution with the best time and space complexity. The solution to Form Array by Concatenating Subarrays of Another Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Form Array by Concatenating Subarrays of Another Array
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.
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).
1764. Form Array by Concatenating Subarrays of Another Array LeetCode Solution in C++
class Solution {
public:
bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
int i = 0; // groups' index
int j = 0; // nums' index
while (i < groups.size() && j < nums.size())
if (isMatch(groups[i], nums, j)) {
j += groups[i].size();
++i;
} else {
++j;
}
return i == groups.size();
}
private:
// Returns true if group == nums[j..j + |group|].
bool isMatch(const vector<int>& group, const vector<int>& nums, int j) {
if (j + group.size() > nums.size())
return false;
for (int i = 0; i < group.size(); ++i)
if (group[i] != nums[j + i])
return false;
return true;
}
}; /* code provided by PROGIEZ */
1764. Form Array by Concatenating Subarrays of Another Array LeetCode Solution in Java
class Solution {
public boolean canChoose(int[][] groups, int[] nums) {
int i = 0; // groups' index
int j = 0; // nums' index
while (i < groups.length && j < nums.length)
if (isMatch(groups[i], nums, j)) {
j += groups[i].length;
++i;
} else {
++j;
}
return i == groups.length;
}
// Returns true if group == nums[j..j + |group|].
private boolean isMatch(int[] group, int[] nums, int j) {
if (j + group.length > nums.length)
return false;
for (int i = 0; i < group.length; ++i)
if (group[i] != nums[j + i])
return false;
return true;
}
} // code provided by PROGIEZ
1764. Form Array by Concatenating Subarrays of Another Array LeetCode Solution in Python
class Solution:
def canChoose(self, groups: list[list[int]], nums: list[int]) -> bool:
i = 0 # groups' index
j = 0 # nums' index
while i < len(groups) and j < len(nums):
if self._isMatch(groups[i], nums, j):
j += len(groups[i])
i += 1
else:
j += 1
return i == len(groups)
# Returns True if group == nums[j..j + |group|].
def _isMatch(self, group: list[int], nums: list[int], j: int) -> bool:
if j + |group | > len(nums):
return False
for i, g in enumerate(group):
if g != nums[j + i]:
return False
return True # code by PROGIEZ
