Skip to content

1764. Form Array by Concatenating Subarrays of Another Array 👍

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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