SDE - 1

1. In this approach we will use BFS (breadth first search) to find all possible paths.

2. We will make a queue which contains the following information : 

a) Vector that stores the path up to a certain cell.

b) coordinates of the cell.

3. We will start from the top-left cell and push cell value and coordinates in the queue.

4. We will keep on exploring right and down cell (if possible) until queue is not empty 

and push them in the queue by updating the current cell vector.

5. If we reach the last cell then we have got one answer and we will print the answer vector.

Idea is to solve the problem using the greedy approach which is the same as Activity Selection Problem.

1. Sort all pairs(Meetings) in increasing order of second number(Finish time) of each pair.

2. Select first meeting of sorted pair as the first Meeting in the room and push it into result vector and set a variable time_limit with the second value(Finishing time) of the first selected meeting.

3. Iterate from the second pair to last pair of the array and if the value of the first element(Starting time of meeting) of the current pair is greater then previously selected pair finish time (time_limit) then select the current pair and update the result vector (push selected meeting number into vector) and variable time_limit.
.
4. Print the Order of meeting from vector.

In the Dynamic programming we will work considering the same cases as mentioned in the recursive approach. In a DP[][] table let’s consider all the possible weights from ‘1’ to ‘W’ as the columns and weights that can be kept as the rows. 

The state DP[i][j] will denote maximum value of ‘j-weight’ considering all values from ‘1 to ith’. So if we consider ‘wi’ (weight in ‘ith’ row) we can fill it in all columns which have ‘weight values > wi’. Now two possibilities can take place: 

1. Fill ‘wi’ in the given column.

2. Do not fill ‘wi’ in the given column.

Now we have to take a maximum of these two possibilities, formally if we do not fill ‘ith’ weight in ‘jth’ column then DP[i][j] state will be same as DP[i-1][j] but if we fill the weight, DP[i][j] will be equal to the value of ‘wi’+ value of the column weighing ‘j-wi’ in the previous row. So we take the maximum of these two possibilities to fill the current state.

The problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components.

1. Check If the left and right pointer elements are negative then simply increment the left pointer.

2. Otherwise, if the left element is positive and the right element is negative then simply swap the elements, and simultaneously increment and decrement the left and right pointers.

3. Else if the left element is positive and the right element is also positive then simply decrement the right pointer.

4. Repeat the above 3 steps until the left pointer ≤ right pointer.

For each node there can be four ways that the max path goes through the node: 
1. Node only 
2. Max path through Left Child + Node 
3. Max path through Right Child + Node 
4. Max path through Left Child + Node + Max path through Right Child
The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. In below code, this sum is stored in ‘max_single’ and returned by the recursive function.