SDE - 1

Approach (Iterative DP ) : 

1) For each cell, let’s compute the answer in a top-down fashion, starting from the top leftmost cells. We create a ‘dp’ table of dimensions X*Y to store these results. 

2) As we compute the results for the top leftmost cells first, when we come to cell (i, j), we already have the results for cells (i-1, j), (i, j-1) and (i-1, j-1) stored in the dp table (provided they do not violate the matrix boundaries). 

3) This allows us to compute results for the current cell in O(1) time.


TC : O(X*Y), where X and Y are the coordinates of the destination cell.
SC : O(X*Y)

Approach : I solved this problem using BFS.

Breadth-First-Search considers all the paths starting from the source and moves ahead one unit in all those paths at
the same time. This makes sure that the first time when the destination is visited, it is the path with the shortest
length.

Steps :

1) Create an empty queue and enqueue source cell and mark it as visited

2) Declare a ‘STEPS’ variable, to keep track of the length of the path so far

3) Loop in level order till the queue is not empty
3.1) Fetch the front cell from the queue
3.2) If the fetched cell is the destination cell, return ‘STEPS’
3.3) Else for each of the 4 adjacent cells of the current cell, we enqueue each valid cell into the queue
and mark them visited.
3.4) Increment ‘STEPS’ by 1 when all the cells in the current level are processed.

4) If all nodes in the queue are processed and the destination cell is not reached, we return -1.


TC : O(N*M), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.
SC : O(N*M)

Iterative(Without using stack) : 
1) Initialize three pointers prev as NULL, curr as head and next as NULL.

2) Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node

next = curr->next

// Now change next of current
// This is where actual reversing happens

curr->next = prev

// Move prev and curr one step forward
prev = curr
curr = next

3)Finally the prev pointer contains our head , i,e. ,head=prev .

TC : O(n)
SC: O(1)



Recursive:

1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer

TC:O(n)
SC:O(n)



Iterative(Using Stack):

1) Store the nodes(values and address) in the stack until all the values are entered.
2) Once all entries are done, Update the Head pointer to the last location(i.e the last value).
3) Start popping the nodes(value and address) and store them in the same order until the stack is empty.
4) Update the next pointer of last Node in the stack by NULL.

TC: O(n)
SC:O(n)

Approach (Using Union-Find Algo) :

1) We initialise two arrays ‘PARENT’ and ‘RANK’ to keep track of the parent and rank of the subsets. Here rank
denotes the depth of the tree (subset).

2) Now we will iterate through all edges of the graph:
2.1) Find the parent of both vertices (say ‘PARENT1’ and ‘PARENT2’).

2.2) If ‘PARENT1’ == ‘PARENT2’
Return “Yes”. Here, ‘PARENT1’ == ‘PARENT2’ represents that both subsets are initially connected and now we have
another edge connecting them. Hence a cycle exists.

2.3) Else If ‘PARENT1’ != ‘PARENT2’
Union both subsets into a single set. We are doing this because we have two subsets and an edge connecting them.
Now both subsets combine and become a single subset.

3) Finally, return “No”.


TC : O(M * logN), where N is the number of vertices and M is the number of edges in the graph.
SC : O(N)

Approach : 

1) The idea is to create a 2-D array ‘result’ of size size (N + 1) * (W + 1).

2) Initially, all the elements of the ‘result’ matrix will be 0.

3) Now, the value result[i][j] denotes the maximum profit the thief can earn considering upto first 'i' items whose combined weight is less than or equal to 'j'.

4) The detailed algorithm to fill the ‘result’ matrix is as follows:
L1 : Run a loop from i = 1 to N to consider all the items.
L2 : Run a loop from j = 0 to W to consider all weights from 0 to maximum capacity W.

If the weight of the current item is more than j, we can not include it. 
Thus, result[i][j] = result[i - 1][j].

Else, find the maximum profit obtained by either including the current item or excluding the current item.
i.e. result[i][j] = max(result[i - 1][j], values[i] + result[i - 1][j - weights[i]]). 

5) Return result[N][W], the final profit that the thief can make.


TC : O(N*W), where N is the number of items and W is the maximum capacity of the knapsack.
SC : O(N*W)

Approach :

1) We will first sort the intervals by non-decreasing order of their start time.

2) Then we will add the first interval to our resultant list.

3) Now, for each of the next intervals, we will check whether the current interval is overlapping with the last interval in
our resultant list.

4) If it is overlapping then we will update the finish time of the last interval in the list by the maximum of the finish time
of both overlapping intervals.

5) Otherwise, we will add the current interval to the list.


TC : O(N * log(N)), where N = number of intervals
SC : O(1)

1) OOPs is very helpful in solving very complex level of problems.
2) Highly complex programs can be created, handled, and maintained easily using object-oriented programming.
3) OOPs, promote code reuse, thereby reducing redundancy.
4) OOPs also helps to hide the unnecessary details with the help of Data Abstraction.
5) OOPs, are based on a bottom-up approach, unlike the Structural programming paradigm, which uses a top-down
approach.
6) Polymorphism offers a lot of flexibility in OOPs.

Access specifiers, as the name suggests, are a special type of keywords, which are used to control or specify the
accessibility of entities like classes, methods, etc. Some of the access specifiers or access modifiers include “private”,
“public”, etc. These access specifiers also play a very vital role in achieving Encapsulation - one of the major features
of OOPs.