[Java, C++] Brute force, HashMap and Binary Search
Brute Force\n\n\nSince the input size is small, brute force works.\n Keep a pointer arrPt to keep track of our progress in arr. If it reaches the end of arr, it
### Brute Force\n\n\nSince the input size is small, brute force works.\n* Keep a pointer `arrPt` to keep track of our progress in `arr`. If it reaches the end of `arr`, it means `arr` can be formed by concatenating the subarrays in `pieces`.\n* We have to find the subarray in `pieces` starting with the element pointed by `arrPt`. If not found, we can immediately return `false`. Otherwise, iterate over the subarray found, and check if subsequent elements are matching the ones in `arr` \n\n\n#### Java\n\n\n```java\npublic boolean canFormArray(int[] arr, int[][] pieces) {\n\tfinal int len = arr.length;\n\t\n\tint arrPt = 0;\n\t\n\twhile (arrPt < len) {\n\t\tint prior = arrPt;\n\t\t\n\t\tfor (int[] piece: pieces) {\n\t\t\t//\tFound the subpiece starting with the element in arr\n\t\t\tif (piece[0] == arr[arrPt] ) {\n\t\t\t\t//\tIterate through the elements in subpiece, checking if it matches the order in arr\n\t\t\t\tfor(int i: piece) if (i != arr[arrPt++] ) return false;\n\t\t\t\t//\tAll elements in subpiece matches. Break out of the loop\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\t//\tIf the pointer doesn\'t move after searching for subarray,\n\t\t//\tit means subarray not found. Return false.\n\t\tif (prior == arrPt) return false;\n\t}\n\treturn true;\n}\n```\n\n\n#### C++\n\n\n```cpp\nbool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {\n\tconst int len = arr.size();\n\n\tint arrPt = 0;\n\n\twhile (arrPt < len) {\n\t\tint prior = arrPt;\n\n\t\tfor (auto& piece : pieces) {\n\t\t\t//\tFound the subpiece starting with the element in arr\n\t\t\tif (piece[0] == arr[arrPt]) {\n\t\t\t\t//\tIterate through the elements in subpiece, checking if it matches the order in arr\n\t\t\t\tfor (int i : piece) if (i != arr[arrPt++]) return false;\n\t\t\t\t//\tAll elements in subpiece matches. Break out of the loop\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\t//\tIf the pointer doesn\'t move after searching for subarray,\n\t\t//\tit means subarray not found. Return false.\n\t\tif (prior == arrPt) return false;\n\t}\n\treturn true;\n}\n```\n\n---\n\n### Hash Map\n\n\n* Instead of having to iterate through the `pieces` array everytime to look for the subpiece stating with element pointed by `arrPt`, we can use extra space to be able to retrieve the subpiece in O(1) time.\n* Since the input size is small, we can just use an array in place of `Hashmap` or `unordered_map`.\n\n\n#### Java\n\n\n```java\npublic boolean canFormArray(int[] arr, int[][] pieces) {\n\tfinal int len = arr.length;\n\n\tint[][] map = new int[101][];\n\tfor (int[] p: pieces) map[ p[0] ] = p;\n\n\tint arrPt = 0;\n\n\twhile (arrPt < len) {\n\t\t//\tNo subpiece starts with the element currently pointed in arr.\n\t\tif (map[ arr[arrPt] ] == null) return false;\n\n\t\t//\tOtherwise iterate through the subpiece, checking each element one by one\n\t\tfor (int i: map[ arr[arrPt]] )\n\t\t\tif ( arr[arrPt++] != i) return false;\n\t}\n\n\treturn true;\t\n}\n```\n\n\n#### C++ (Using unordered_map)\n\n\n```cpp\nbool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {\n\tconst int len = arr.size();\n\n\tunordered_map<int, vector<int>*> map;\n\tfor (auto& piece : pieces)\n\t\tmap[piece[0]] = &piece;\n\n\tint arrPt = 0;\n\n\twhile (arrPt < len) {\n\t\tauto found = map.find(arr[arrPt]);\n\t\tif (found == map.end()) return false;\n\n\t\tfor (int i : *(found->second)) {\n\t\t\tif (arr[arrPt++] != i) return false;\n\t\t}\n\t}\n\n\treturn true;\n}\n```\n\n---\n\n### Binary Search\n\n* By sorting the `pieces` based on the subarray\'s first element, we can now perform binary search whenever we want to search for subarray.\n\n#### Java\n\n```java\npublic boolean canFormArray(int[]arr, int[][] pieces) {\n\tArrays.sort( pieces, (x,y)-> {\n\t\treturn x[0] - y[0];\n\t});\n\n\tfinal int len = arr.length;\n\tint arrPt = 0;\n\n\twhile (arrPt < len) {\n\t\tint[] res = binarySearch( pieces, arr[arrPt] );\n\t\tif (res == null) return false;\t\t//\tNot found. Return false\n\n\t\tfor (int i: res)\n\t\t\tif (i != arr[arrPt++] ) return false;\n\t}\n\treturn true;\n}\n\nprivate int[] binarySearch(int[][] pieces, int val) {\n\tint left = 0;\n\tint right = pieces.length - 1;\n\n\twhile (left < right) {\n\t\tint mid = left + (right - left) / 2;\n\n\t\tif (pieces[mid][0] < val) \n\t\t\tleft = mid + 1;\n\t\telse right = mid;\n\t}\n\n\t//\tIf the subpiece is not what we looking for, return null\n\treturn pieces[left][0] == val? pieces[left]: null;\n}\n```\n\n#### C++\n\n```cpp\nbool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {\n\tsort(pieces.begin(), pieces.end(), [](auto& x, auto& y)->bool {\n\t\treturn x[0] - y[0] < 0;\n\t});\n\n\tconst int len = arr.size();\n\tint arrPt = 0;\n\n\twhile (arrPt < len) {\n\t\tauto res = binarySearch(pieces, arr[arrPt]);\n\t\tif (!res) return false;\n\n\t\tfor (int i : *res ) {\n\t\t\tif (i != arr[arrPt++]) return false;\n\t\t}\n\t}\n\treturn true;\n}\nvector<int>* binarySearch(vector<vector<int>>& pieces, int val) {\n\tint left = 0;\n\tint right = pieces.size() - 1;\n\n\twhile (left < right) {\n\t\tint mid = left + (right - left) / 2;\n\n\t\tif (pieces[mid][0] < val)\n\t\t\tleft = mid + 1;\n\t\telse right = mid;\n\t}\n\n\treturn pieces[left][0] == val ? &pieces[left] : nullptr ;\n}\n```\n
[]