Uploaded March 2019 | Updated November 2026, 1 hour ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: There are 2 versions.
Version 1: Every row is sorted left to right in non-decreasing order. The first integer of each row is greater or equal to the last integer of the previous row.
Version 2: Every row is sorted left to right in non-decreasing order. Every column is sorted top to bottom in non-decreasing order. There are no guarantees that the first item of any row or column relates to the last item in the previous row or column.
Sorted. Binary search is very likely. Investigate, how do we reduce our decision space?
Our first answer does not need to be logarithmic (it is so crucial you understand logarithms and what they mean....you need to know your complexities to refine answers and notice avenues to better solutions).
The key to search problems is that you notice the fundamental decision we can make to reduce the problem.
...more notes I wrote...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: There are 2 versions.
Version 1: Every row is sorted left to right in non-decreasing order. The first integer of each row is greater or equal to the last integer of the previous row.
Version 2: Every row is sorted left to right in non-decreasing order. Every column is sorted top to bottom in non-decreasing order. There are no guarantees that the first item of any row or column relates to the last item in the previous row or column.
Sorted. Binary search is very likely. Investigate, how do we reduce our decision space?
Our first answer does not need to be logarithmic (it is so crucial you understand logarithms and what they mean....you need to know your complexities to refine answers and notice avenues to better solutions).
The key to search problems is that you notice the fundamental decision we can make to reduce the problem.
...more notes I wrote...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw


![Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given n, how many structurally unique BSTs (binary search trees) that store values 1 ... n?
Catalan Numbers: https://en.wikipedia.org/wiki/Catalan_number
Define G(n): the number of unique BST for a sequence of length n.
G(0) = 1
G(1) = 1
For each element, we can place it and recurse on the left an right not including that number we choose to root that subtree.
Define F(i,n): the number of unique BST, where the number i is served as the root of BST (1 is less than or equal to i which is less than or equal to n).
G(n) = the summation from 1 to n of F(i, n)
When we choose an element to root a subtree from the possible elements to root there, we split the possibilities into a left and a right of the original enumeration.
Example:
n = 5 aka [1, 2, 3, 4, 5]
When evaluating F(3, 5) we will have
a left subtree with [1, 2] aka G(2)
a right subtree with [4, 5] aka G(2)
G(n) evaluates the # of unique trees we can construct from a total of n possible values, regardless of what those values are.
The Realization
We notice that F(i, n) = G(i - 1) * G(n - i)
To get F(i, n) we are considering all combinations of left tree possibilities with all of the right tree possibilities.
These exhaustive pairings between two sets of items is called a cartesian product.
Now we have a new way to express F(i, n)
F(i, n) = G(i - 1) * G(n - i)
G(n) = summation from 1 to n of G(i - 1) * G(n - i)
This now can be solved with DP via top-down recursion or bottom up.
For each G(n) up to our requested n we will solve the G(n) summation equation.
At the end we return the G(n) requested which by the end we will have an answer for.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)](https://i.ytimg.com/vi/GgP75HAvrlY/mqdefault.jpg)







