Form Array by Concatenating Subarrays of Another Array

Problem Id: 1764 Difficulty: Medium Tag: Array Tag: Greedy


Intuition

The difficult part to pass this problem in just one commit without TLE is to calculate the time complexity and judge manually if it will pass the system check in time. Before start to write the code, let's first make every thing clear.

Ideas

Let's start from the input. We are given 2 parameters, groups and nums. Basically, we are asked to judge whether the nums array can be formed by elements in groups plus some useless numbers. For example, given groups [[10, -2], [1, 2, 3, 4]] and nums [-1, 10, -2, 1, 2, 1, 2, 3, 4], we can form nums by groups by this way, [-1, 10, -2, 1, 2, 1, 2, 3, 4].

Time complexity

The basic way (brute force) to solve it is for every index in nums, check if it can match the next array in groups. For example, when i=0, and next array in groups is groups[0]. We check if nums[i:i + len(groups[0])] equals groups[0]. So the worst time complexity is:

O(group[i].length * nums.length)
Manually check time complexity

Now let's consider if this brute force solution can pass the OJ system. The overall operations should be at most around 1,000,000 in order to pass the judge system in time. For this problem, 1 <= sum(groups[i].length) <= 1,000, and 1 <= nums.length <= 1,000. So that the overall time complexity would be group[i].length * nums.length ~= 1,000,000. This is just what we want.

Implementation

So let's implement the code. The variable group_id I used is for marking which array in groups is the next array used for match. start is the index of the start point which we will use in the array nums. Each run of the while loop, I will check if nums[i:i + len(groups[0])] equals groups[0]. And only all array in groups are matched, we will return True.

Solution


class Solution:
    def canChoose(self, groups, nums):
        group_id = 0
        start = 0
        while start < len(nums):
            group = groups[group_id]
            match = True
            for offset in range(len(group)):
                if start + offset >= len(nums):
                    return False
                if group[offset] != nums[start + offset]:
                    match = False
            if match:
                group_id += 1
                start = start + len(group)
            else:
                start += 1
            if group_id >= len(groups):
                return True
        return False