SDE - 1

Maintain a head and a tail pointer on the merged linked list.

Then choose the head of the merged linked list by comparing the first node of both linked lists.

For all subsequent nodes in both lists, you choose the smaller current node link it to the tail of the merged list, and move the current pointer of that list one step forward.

You keep doing this while there are some remaining elements in both lists.

If there are still some elements in only one of the lists, you link this remaining list to the tail of the merged list.

Initially, the merged linked list is NULL.

Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list.

Since it’s the first and only node in the merged list, it will also be the tail.

Then move head1 one step forward.

The number of unique paths from a given cell (i,j) to the end cell is always fixed. So, we don't need to calculate and repeat the same process for a given cell multiple times. We can just store the result calculated for cell (i, j) and use that result in the future whenever required.

Thus, here we use a 2d array dp, where dp[i][j] denotes the number of unique paths from the cell (i, j) to the end cell (m-1, n-1). Once we get an answer for cell (i, j), we store the result in dp[i][j] and reuse it instead of recalculating it.

1. Initialize count = 0
2. Loop through the link list
a. If the count is equal to the passed index then return the current
node
b. Increment count
c. change current to point to next of the current.

Tip 1: Read OS concepts thoroughly.

A graph can be connected or disconnected, can have cycles or loops, and does not necessarily have a root node. A tree is a type of graph that is connected, acyclic (meaning it has no cycles or loops), and has a single root node.

Tip 1: Do practice SQL queries.

There are three solutions to this problem.

Iterative solution using stack: O(n) time and O(n) space;
Recursive solution: O(n) time and O(n) space (function call stack);
Morris traversal: O(n) time and O(1) space.

At each index i, we can either pick that element or not pick it.
If we pick the current element, then all future elements must also be picked since our array needs to be contiguous.
If we had picked any elements till now, we can either end further recursion at any time by returning the sum formed till now or we can choose the current element and recurse further. This denotes two choices either choosing the subarray formed from 1st picked element till now or expanding the subarray by choosing the current element respectively.