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:

Example 2:

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

Merge K sorted list

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Example 1:

Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example 1:

Median of two sorted arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

First missing positive

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Example 2:

Example 3:

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero…

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading…

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.

Time : O(n²)

Space: O(1)

Approach 2:

Using hashmap

Use the hash set to store the previously visited node

Time : O(n)

Space: O(n)

Floyd’s Cycle Detection algorithm

Given a linked list , our aim is to detect whether or not it contain a cycle. If it contain a cycle then we are required to find the start node of the cycle.

This can be solved using Floyd’s Cycle Detection algorithm

We keep 2 pointers slow and fast… Dhanarajappu

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