Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1764.html

1764. Form Array by Concatenating Subarrays of Another Array

Level

Medium

Description

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 i-th subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)-th subarray appears before the i-th 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 <= 10^3
  • 1 <= groups[i].length, sum(groups[i].length) <= 10^3
  • 1 <= nums.length <= 10^3
  • -10^7 <= groups[i][j], nums[k] <= 10^7

Solution

Loop over groups. For each group in groups, find the first occurrence of group in nums. After the start index of group in nums is found, update the minimum possible start index in nums and check the remaining groups. The minimum possible start index of the next group in nums must be greater than the last index in nums of group.

If all groups’ occurrences in nums can be found, return true. Otherwise, return false.

  • class Solution {
    public boolean canChoose(int[][] groups, int[] nums) {
        int length = nums.length;
        int groupsCount = groups.length;
        int curIndex = 0;
        for (int i = 0; i < groupsCount; i++) {
            int[] group = groups[i];
            int groupStart = findGroupStart(group, nums, curIndex);
            if (groupStart < 0)
                return false;
            curIndex = groupStart + group.length;
            if (curIndex >= length && i < groupsCount - 1)
                return false;
        }
        return true;
    }

    public int findGroupStart(int[] group, int[] nums, int start) {
        int length = nums.length;
        int groupLength = group.length;
        int maxStart = length - groupLength;
        for (int i = start; i <= maxStart; i++) {
            boolean flag = true;
            for (int j = 0; j < groupLength; j++) {
                if (nums[i + j] != group[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return i;
        }
        return -1;
    }
}

############

class Solution {
    public boolean canChoose(int[][] groups, int[] nums) {
        int n = groups.length, m = nums.length;
        int i = 0;
        for (int j = 0; i < n && j < m;) {
            if (check(groups[i], nums, j)) {
                j += groups[i].length;
                ++i;
            } else {
                ++j;
            }
        }
        return i == n;
    }

    private boolean check(int[] a, int[] b, int j) {
        int m = a.length, n = b.length;
        int i = 0;
        for (; i < m && j < n; ++i, ++j) {
            if (a[i] != b[j]) {
                return false;
            }
        }
        return i == m;
    }
}

  • // OJ: https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array/
// Time: O(MLN) where M is the length of G, L is the max length of arrays in G, and N is the length of A
// Space: O(M)
class Solution {
    bool good(vector<vector<int>>& G, vector<int>& A, int gi, int i) {
        auto &g = G[gi];
        for (int j = 0; j < g.size(); ++j) {
            if (i + j >= A.size() || g[j] != A[i + j]) return false;
        }
        if (gi == G.size() - 1) return true;
        for (int j = i + g.size(); j < A.size(); ++j) {
            if (good(G, A,  gi + 1, j)) return true;
        }
        return false;
    }
public:
    bool canChoose(vector<vector<int>>& G, vector<int>& A) {
        int i = 0, j = 0, M = G.size(), N = A.size(), len = 0;
        for (auto &v : G) len += v.size();
        if (len > A.size()) return false;
        for (int i = 0; i < N; ++i) {
            if (good(G, A, 0, i)) return true;
        }
        return false;
    }
};

  • class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        n, m = len(groups), len(nums)
        i = j = 0
        while i < n and j < m:
            g = groups[i]
            if g == nums[j : j + len(g)]:
                j += len(g)
                i += 1
            else:
                j += 1
        return i == n

############

# 1764. Form Array by Concatenating Subarrays of Another Array
# https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array/

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        i = 0
        
        for grp in groups:
            for ii in range(i, len(nums)):
                if nums[ii: ii + len(grp)] == grp:
                    i = ii + len(grp)
                    break
            else:
                return False
        
        return True


  • func canChoose(groups [][]int, nums []int) bool {
	check := func(a, b []int, j int) bool {
		m, n := len(a), len(b)
		i := 0
		for ; i < m && j < n; i, j = i+1, j+1 {
			if a[i] != b[j] {
				return false
			}
		}
		return i == m
	}
	n, m := len(groups), len(nums)
	i := 0
	for j := 0; i < n && j < m; {
		if check(groups[i], nums, j) {
			j += len(groups[i])
			i++
		} else {
			j++
		}
	}
	return i == n
}

All Problems

All Solutions