{"id":7320,"date":"2020-08-30T01:48:13","date_gmt":"2020-08-30T08:48:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7320"},"modified":"2020-08-30T12:27:45","modified_gmt":"2020-08-30T19:27:45","slug":"leetcode-1569-number-of-ways-to-reorder-array-to-get-same-bst","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-1569-number-of-ways-to-reorder-array-to-get-same-bst\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST"},"content":{"rendered":"\n

Given an array nums<\/code> that represents a permutation of integers from 1<\/code> to n<\/code>. We are going to construct a binary search tree (BST) by inserting the elements of nums<\/code> in order into an initially empty BST. Find the number of different ways to reorder nums<\/code> so that the constructed BST is identical to that formed from the original array nums<\/code>.<\/p>\n\n\n\n

For example, given nums = [2,1,3]<\/code>, we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1]<\/code> also yields the same BST but [3,2,1]<\/code> yields a different BST.<\/p>\n\n\n\n

Return the number of ways to reorder<\/em> nums<\/code> such that the BST formed is identical to the original BST formed from<\/em> nums<\/code>.<\/p>\n\n\n\n

Since the answer may be very large, return it modulo <\/strong>10^9 + 7<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [2,1,3]\nOutput:<\/strong> 1\nExplanation: <\/strong>We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [3,4,5,1,2]\nOutput:<\/strong> 5\nExplanation: <\/strong>The following 5 arrays will yield the same BST: \n[3,1,2,4,5]\n[3,1,4,2,5]\n[3,1,4,5,2]\n[3,4,1,2,5]\n[3,4,1,5,2]\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [1,2,3]\nOutput:<\/strong> 0\nExplanation: <\/strong>There are no other orderings of nums that will yield the same BST.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> nums = [3,1,2,5,4,6]\nOutput:<\/strong> 19\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]\nOutput:<\/strong> 216212978\nExplanation: <\/strong>The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 1000<\/code><\/li>
  • 1 <= nums[i] <= nums.length<\/code><\/li>
  • All integers in nums<\/code> are distinct<\/strong>.<\/li><\/ul>\n\n\n\n
    Solution: Recursion + Combinatorics<\/strong><\/h2>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l \/ r nodes, we have ways(left) \/ ways(right) different ways to re-arrange those nodes. So the total # of ways is:
    C(l + r, l) * ways(l) * ways(r)
    Don’t forget to minus one for the final answer.<\/p>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(n^2)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int numOfWays(vector& nums) {\n    const int n = nums.size();\n    const int kMod = 1e9 + 7;\n    vector> cnk(n + 1, vector(n + 1, 1));    \n    for (int i = 1; i <= n; ++i)      \n      for (int j = 1; j < i; ++j)\n        cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % kMod;    \n    function)> trees = [&](const vector& nums) {\n      const int n = nums.size();\n      if (n <= 2) return 1;\n      vector left;\n      vector right;\n      for (int i = 1; i < nums.size(); ++i)\n        if (nums[i] < nums[0]) left.push_back(nums[i]);\n        else right.push_back(nums[i]);\n      long ans = cnk[n - 1][left.size()];\n      ans = (ans * trees(left)) % kMod;      \n      ans = (ans * trees(right)) % kMod;      \n      return static_cast(ans);\n    };\n    return trees(nums) - 1;\n  } \n};\n<\/pre>\n\n<\/div>
    python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def numOfWays(self, nums: List[int]) -> int:\n    def ways(nums):\n      if len(nums) <= 2: return 1\n      l = [x for x in nums if x < nums[0]]\n      r = [x for x in nums if x > nums[0]]\n      return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)\n    return (ways(nums) - 1) % (10**9 + 7)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[122,217,31,17],"class_list":["post-7320","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-combination","tag-hard","tag-math","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7320","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7320"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7320\/revisions"}],"predecessor-version":[{"id":7325,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7320\/revisions\/7325"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7320"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}