SDE - 1

Step 1 : create a stack that will store the current asteroid.
Step 2 : if the current asteroid is positive we will push it inside our stack.
Step 3 : else we will pop while the top element is greater.

vector asteroidCollision(vector& asteroids) {
stack st;
int n = asteroids.size();
for(int i = 0;i 0 ) {
st.push(asteroids[i]);
}
else {
while(st.size() != 0 && st.top() > 0 && -asteroids[i] > st.top()) {
st.pop();
}

if(st.size() != 0 && st.top() == -asteroids[i])
st.pop();
else if(st.size() == 0 || st.top()<0)
st.push(asteroids[i]);
}
}
vector ans(st.size(),0);
int i = st.size()-1;
while(i>=0) {
ans[i--] = st.top();
st.pop();
}
return ans;
}

Naive approach: The simple idea is to traverse the array and to search elements one by one.

Algorithm: 
Run a nested loop, outer loop for row and inner loop for the column
Check every element with x and if the element is found then print “element found”
If the element is not found, then print “element not found”.

Efficient approach: The simple idea is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases. 

The given number is greater than the current number: This will ensure that all the elements in the current row are smaller than the given number as the pointer is already at the right-most elements and the row is sorted. Thus, the entire row gets eliminated and continues the search for the next row. Here, elimination means that a row needs not be searched.
The given number is smaller than the current number: This will ensure that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continues the search for the previous column, i.e. the column on the immediate left.
The given number is equal to the current number: This will end the search.

Algorithm: 
Let the given element be x, create two variable i = 0, j = n-1 as index of row and column
Run a loop until i = n
Check if the current element is greater than x then decrease the count of j. Exclude the current column.
Check if the current element is less than x then increase the count of i. Exclude the current row.
If the element is equal, then print the position and end.

int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;

int smallest = mat[0][0], largest = mat[n - 1][n - 1];
if (x < smallest || x > largest)
return -1;

int i = 0, j = n - 1;
while (i < n && j >= 0)
{
if (mat[i][j] == x)
{
return 1;
}
if (mat[i][j] > x)
j--;

else
i++;
}

return 0;
}

Naive Approach: Given an array, the solution is to find the maximum sum subsequence where no two selected elements are adjacent. So the approach to the problem is a recursive solution. So there are two cases. 


If an element is selected then the next element cannot be selected.
if an element is not selected then the next element can be selected.

Method 2: Dynamic Programming : Top Down Approach

So the recursive solution can easily be devised. The sub-problems can be stored thus reducing the complexity and converting the recursive solution to a Dynamic programming problem.

Method 3: Dynamic Programming : Bottom Up Approach

So the recursive solution can easily be devised. The sub-problems can be stored thus reducing the complexity and converting the recursive solution to a Dynamic programming problem.

Efficient Approach: By carefully observing the DP array, it can be seen that the values of previous two indices matter while calculating the value for an index. To replace the total DP array by two variables.
Algorithm: 


Tackle some basic cases, if the length of the array is 0, print 0, if the length of the array is 1, print the first element, if the length of the array is 2, print maximum of two elements.
Create two variables value1 and value2 value1 as array[0] and value2 as maximum of array[0] and array[1] and a variable max_val to store the answer
Traverse the array from the second element (2nd index) to the end of array.
For every index, update max_val as maximum of value1 + array[i] and value2, this step defines the two cases, if an element is selected then the previous element cannot be selected and if an element is not selected then the previous element can be selected.
For every index, Update value1 = value2 and value2 = max_val
Print the value of max_val
int maxLoot(int* hval, int n)
{
if (n == 0)
return 0;

int value1 = hval[0];
if (n == 1)
return value1;

int value2 = max(hval[0], hval[1]);
if (n == 2)
return value2;

int max_val;

for (int i = 2; i < n; i++) {
max_val = max(hval[i] + value1, value2);
value1 = value2;
value2 = max_val;
}

return max_val;
}

Step 1 : Use DFS to mark and travel to each adjacent land.
Step 2 : Each time a new land is found increment our answer.

void helper(vector>& grid, int i, int j, int m, int n, vector>& vis){
vis[i][j] = true;
if(i+1 < m && grid[i+1][j] == '1' && vis[i+1][j] == false){
helper(grid, i+1, j, m, n, vis);
}
if(j - 1 >= 0 && grid[i][j-1] == '1' && vis[i][j-1] == false){
helper(grid, i, j-1, m, n, vis);
}
if(i - 1 >= 0 && grid[i-1][j] == '1' && vis[i-1][j] == false){
helper(grid, i-1, j, m, n, vis);
}
if(j + 1 < n && grid[i][j+1] == '1' && vis[i][j+1] == false){
helper(grid, i, j+1, m, n, vis);
}
}
int numIslands(vector>& grid) {
int ans = 0;
int m=grid.size();
int n = grid[0].size();
vector> vis(n, vector (m));
for(int i=0;i for(int j=0;j if(grid[i][j] == '1' && vis[i][j] == false){
ans++;
helper(grid, i, j, m, n, vis);
}
}
}
return ans;
}

Step 1 : same as normal binary tree height but the only thing different is to find leaf node.
Step 2 : for that we will just check our right child -> left == curr && left child -> right == curr

The idea is to follow similar approach as we do for finding height of a normal binary tree. We recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. But left and right child of a leaf node are null for normal binary trees. But, here leaf node is a circular doubly linked list node. So for a node to be a leaf node, we check if node’s left’s right is pointing to the node and its right’s left is also pointing to the node itself.

bool isLeaf(Node* node)
{
return node->left && node->left->right == node
&& node->right && node->right->left == node;
}

Nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(Node* node)
{
if (node == NULL)
return 0;

if (isLeaf(node))
return 1;

return 1
+ max(maxDepth(node->left),
maxDepth(node->right));
}

Step 1 : Recursive implementation: 
The idea is simple, we consider each prefix and search it in dictionary. If the prefix is present in dictionary, we recur for rest of the string (or suffix).
If the recursive call for suffix returns true, we return true, otherwise we try next prefix. If we have tried all prefixes and none of them resulted in a solution, we return false.
Step 2 : memorize your code
Step 3 : Tabulation
In this approach, apart from the dp table, we also maintain all the indexes which have matched earlier. Then we will check the substrings from those indexes to the current index. If anyone of that matches then we can divide the string up to that index.
In this program, we are using some extra space. However, its time complexity is O(n*s) where s is the length of the largest string in the dictionary and n is the length of the given string.

int dictionaryContains(string word)
{
string dictionary[]
= { "mobile", "samsung", "sam", "sung", "man",
"mango", "icecream", "and", "go", "i",
"like", "ice", "cream" };
int size = sizeof(dictionary) / sizeof(dictionary[0]);
for (int i = 0; i < size; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}

bool wordBreak(string s)
{
int n = s.size();
if (n == 0)
return true;

vector dp(n + 1, 0); // Initialize all values
vector matched_index;
matched_index.push_back(-1);

for (int i = 0; i < n; i++) {
int msize = matched_index.size();

int f = 0;

for (int j = msize - 1; j >= 0; j--) {

string sb = s.substr(matched_index[j] + 1,
i - matched_index[j]);

if (dictionaryContains(sb)) {
f = 1;
break;
}
}
if (f == 1) {
dp[i] = 1;
matched_index.push_back(i);
}
}
return dp[n - 1];
}

Method 1 (Simple) 
Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.

Method 2 (Using Stack) 

Push the first element to stack.
Pick rest of the elements one by one and follow the following steps in loop. 
Mark the current element as next.
If stack is not empty, compare top element of stack with next.
If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
Finally, push the next in the stack.
After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.


void printNGE(int arr[], int n)
{
stack s;

s.push(arr[0]);

for (int i = 1; i < n; i++)
{

if (s.empty()) {
s.push(arr[i]);
continue;
}

while (s.empty() == false
&& s.top() < arr[i])
{
s.pop();
}

s.push(arr[i]);
}

while (s.empty() == false) {
s.pop();
}
}

Step 1 : This problem can be solved using two stacks. Assume the two stacks are current: currentlevel and nextlevel. 
Step 2 : We would also need a variable to keep track of the current level order(whether it is left to right or right to left). We pop from the currentlevel stack and print the nodes value. Whenever the current level order is from left to right, push the nodes left child, then its right child to the stack nextlevel. Since a stack is a LIFO(Last-In-First_out) structure, next time when nodes are popped off nextlevel, it will be in the reverse order. On the other hand, when the current level order is from right to left, we would push the nodes right child first, then its left child.
step3: Finally, do-not forget to swap those two stacks at the end of each level(i.e., when current level is empty)

void zizagtraversal(struct Node* root)
{
if (!root)
return;

stack currentlevel;
stack nextlevel;

currentlevel.push(root);
bool lefttoright = true;
while (!currentlevel.empty()) {
struct Node* temp = currentlevel.top();
currentlevel.pop();

if (temp) {


if (lefttoright) {
if (temp->left)
nextlevel.push(temp->left);
if (temp->right)
nextlevel.push(temp->right);
}
else {
if (temp->right)
nextlevel.push(temp->right);
if (temp->left)
nextlevel.push(temp->left);
}
}

if (currentlevel.empty()) {
lefttoright = !lefttoright;
swap(currentlevel, nextlevel);
}
}
}

Step 1 : A simple solution is consider every subarray and count 1’s in every subarray. Finally return return size of largest subarray with all 1’s.
Step 2 : An efficient solution is traverse array from left to right. If we see a 1, we increment count and compare it with maximum so far. If we see a 0, we reset count as 0.

int getMaxLength(bool arr[], int n)
{
int count = 0; 
int result = 0; 

for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
count = 0;

else
{
count++;
result = max(result, count);
}
}

return result;
}