Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.
nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,1,3] Output: 1 Explanation: 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.
Example 2:
Input: nums = [3,4,5,1,2] Output: 5 Explanation: The following 5 arrays will yield the same BST: [3,1,2,4,5] [3,1,4,2,5] [3,1,4,5,2] [3,4,1,2,5] [3,4,1,5,2]
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: There are no other orderings of nums that will yield the same BST.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= nums.lengthnums are distinct.Problem summary: 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 an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums. For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST. Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums. Since the answer may be very large, return it modulo 109 + 7.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Dynamic Programming · Tree · Union-Find
[2,1,3]
[3,4,5,1,2]
[1,2,3]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1569: Number of Ways to Reorder Array to Get Same BST
class Solution {
private int[][] c;
private final int mod = (int) 1e9 + 7;
public int numOfWays(int[] nums) {
int n = nums.length;
c = new int[n][n];
c[0][0] = 1;
for (int i = 1; i < n; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
List<Integer> list = new ArrayList<>();
for (int x : nums) {
list.add(x);
}
return (dfs(list) - 1 + mod) % mod;
}
private int dfs(List<Integer> nums) {
if (nums.size() < 2) {
return 1;
}
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for (int x : nums) {
if (x < nums.get(0)) {
left.add(x);
} else if (x > nums.get(0)) {
right.add(x);
}
}
int m = left.size(), n = right.size();
int a = dfs(left), b = dfs(right);
return (int) ((long) a * b % mod * c[m + n][n] % mod);
}
}
// Accepted solution for LeetCode #1569: Number of Ways to Reorder Array to Get Same BST
func numOfWays(nums []int) int {
n := len(nums)
const mod = 1e9 + 7
c := make([][]int, n)
for i := range c {
c[i] = make([]int, n)
}
c[0][0] = 1
for i := 1; i < n; i++ {
c[i][0] = 1
for j := 1; j <= i; j++ {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
}
}
var dfs func(nums []int) int
dfs = func(nums []int) int {
if len(nums) < 2 {
return 1
}
var left, right []int
for _, x := range nums[1:] {
if x < nums[0] {
left = append(left, x)
} else {
right = append(right, x)
}
}
m, n := len(left), len(right)
a, b := dfs(left), dfs(right)
return c[m+n][m] * a % mod * b % mod
}
return (dfs(nums) - 1 + mod) % mod
}
# Accepted solution for LeetCode #1569: Number of Ways to Reorder Array to Get Same BST
class Solution:
def numOfWays(self, nums: List[int]) -> int:
def dfs(nums):
if len(nums) < 2:
return 1
left = [x for x in nums if x < nums[0]]
right = [x for x in nums if x > nums[0]]
m, n = len(left), len(right)
a, b = dfs(left), dfs(right)
return (((c[m + n][m] * a) % mod) * b) % mod
n = len(nums)
mod = 10**9 + 7
c = [[0] * n for _ in range(n)]
c[0][0] = 1
for i in range(1, n):
c[i][0] = 1
for j in range(1, i + 1):
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
return (dfs(nums) - 1 + mod) % mod
// Accepted solution for LeetCode #1569: Number of Ways to Reorder Array to Get Same BST
struct Solution;
const MOD: i64 = 1_000_000_007;
impl Solution {
fn num_of_ways(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut table = vec![];
for i in 0..=n {
table.push(vec![1; i + 1]);
for j in 1..i {
table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % MOD;
}
}
Self::ways(nums, &table) as i32 - 1
}
fn ways(nums: Vec<i32>, table: &[Vec<i64>]) -> i64 {
if nums.is_empty() {
return 1;
}
let root = nums[0];
let left: Vec<i32> = nums.iter().filter(|&&x| x < root).copied().collect();
let right: Vec<i32> = nums.iter().filter(|&&x| x > root).copied().collect();
let l = left.len();
let r = right.len();
let mut res = table[l + r][l];
res %= MOD;
res *= Self::ways(right, table);
res %= MOD;
res *= Self::ways(left, table);
res %= MOD;
res
}
}
#[test]
fn test() {
let nums = vec![2, 1, 3];
let res = 1;
assert_eq!(Solution::num_of_ways(nums), res);
let nums = vec![3, 4, 5, 1, 2];
let res = 5;
assert_eq!(Solution::num_of_ways(nums), res);
let nums = vec![1, 2, 3];
let res = 0;
assert_eq!(Solution::num_of_ways(nums), res);
let nums = vec![3, 1, 2, 5, 4, 6];
let res = 19;
assert_eq!(Solution::num_of_ways(nums), res);
let nums = vec![
9, 4, 2, 1, 3, 6, 5, 7, 8, 14, 11, 10, 12, 13, 16, 15, 17, 18,
];
let res = 216212978;
assert_eq!(Solution::num_of_ways(nums), res);
}
// Accepted solution for LeetCode #1569: Number of Ways to Reorder Array to Get Same BST
function numOfWays(nums: number[]): number {
const n = nums.length;
const mod = 1e9 + 7;
const c = new Array(n).fill(0).map(() => new Array(n).fill(0));
c[0][0] = 1;
for (let i = 1; i < n; ++i) {
c[i][0] = 1;
for (let j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
const dfs = (nums: number[]): number => {
if (nums.length < 2) {
return 1;
}
const left: number[] = [];
const right: number[] = [];
for (let i = 1; i < nums.length; ++i) {
if (nums[i] < nums[0]) {
left.push(nums[i]);
} else {
right.push(nums[i]);
}
}
const m = left.length;
const n = right.length;
const a = dfs(left);
const b = dfs(right);
return Number((BigInt(c[m + n][m]) * BigInt(a) * BigInt(b)) % BigInt(mod));
};
return (dfs(nums) - 1 + mod) % mod;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.