[Python] HashMap Solution O(N) + Follow up question
Problem 1: Special Constraint\n- The integers in arr are distinct.\n- The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the int
**Problem 1: Special Constraint**\n- The integers in `arr` are **distinct**.\n- The integers in `pieces` are **distinct** (i.e., If we flatten pieces in a 1D array, all the integers in this array are **distinct**).\n- `sum(pieces[i].length) == arr.length`.\n\n```python\nclass Solution:\n    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n        map = dict()\n        for p in pieces:\n            map[p[0]] = p\n\n        n = len(arr)\n        i = 0\n        while i < n:\n            if arr[i] not in map:\n                return False\n            p = map[arr[i]]\n            if arr[i:i + len(p)] != p:\n                return False\n            i += len(p)\n        return True\n```\n\n**Complexity**\n- Time: `O(N)`, where `N` is number of elements in array `arr`.\n- Space: `O(N)`\n\n\n**Problem 2: Follow up question**\n- The integers in `arr` can be **duplicated**.\n- The integers in `pieces` can be **duplicated**.\n- `sum(pieces[i].length) != arr.length`.\n\n**Example 1:**\nInput: arr = [4,91,4,64,78], pieces = [[78],[4],[4,64],[91]]\nOutput: true\n\n**Example 2:**\nInput: arr = [4,91,4,64,78], pieces = [[78],[4],[4,64],[91], [5]]\nOutput: false\n\n```python\nclass Solution:\n    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n        pieces.sort(key=lambda x: -len(x))  # Sort by decreasing order of length of pieces to avoid \n        # case an bigger array contains another array, but bigger array is processed later\n\n        m = sum(len(p) for p in pieces)\n        seen = set()\n\n        n = len(arr)\n        i = 0\n        while i < n:\n            good = False\n            for j, p in enumerate(pieces):\n                if j in seen: continue\n                if arr[i:i + len(p)] == p:\n                    good = True\n                    i += len(p)\n                    seen.add(j)\n                    break\n            if not good: return False\n        return i == m\n```\n\nComplexity:\n- Time: `O(NlogN + N*M)`, where `N` is number of elements in array `arr`, `M` is number of elements in `pieces` after flat into 1D.\n- Space: `O(M)`
[]