96. Unique Binary Search Trees

Given an integer `n`, return the number of structurally unique BST's (binary search trees) which has exactly `n` nodes of unique values from `1` to `n`.

Example 1:

`Input: n = 3Output: 5`

Example 2:

`Input: n = 1Output: 1`

Constraints:

• `1 <= n <= 19`

Approach 1:

Dynamic Programming

As we can see ,

• number of unique BST for a tree with n=1 is 1
• number of unique BST for a tree with n=2 is 2
• number of unique BST for a tree with n=3 is

Remove duplicate copies of a number from unsorted linked list

Remove the duplicate copies of number from the unsorted linked list, means only keep the a number 1 time , in the linked list

What if extra space (temporary buffer can’t be used)?

Approach 1:

If temporary buffer can’t be used , then this is solved in O(n²) time and O(1) space. For each of the current node , see if any node succeeding that node , has the same value. And remove all those nodes.

`def remove_dup(self,head):   curr = head    while(curr):     runner=curr     while(runner.next):       if runner.next.data==curr.data:         runner.next=runner.next.next       else:         runner=runner.next     curr=curr.next   return head`

Time : O(n²)

Space: O(1)

Approach 2:

Using hashmap

Use the hash set to store the previously visited node

`def remove_dup(self,head):  curr = head   while(curr):     if curr.data in hash_set:        prev.next=curr.next     else:        hash_set.add(curr.data)        prev=curr     curr=curr.next  return head`

Time : O(n)

Space: O(n)

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.