Find length of the longest consecutive path from a given starting character

Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. It is allowed to move in all 8 directions from a cell.

example:

for mat[][]={{a,c,d},
                     {h,b,e},
                     {i,g,f}} 
and input character 'e' o/p will be 5

At first this problem is looking easy (Indeed this is) by simply finding the next character via doing a 8 way recursion, this is doable this way but we can do it more efficiently by using dynamic programing, there can be some subproblem while we are searching for a path so we will store that paths in our dp matrix and will use it in between.

simple solution in java 

class SearchPath

{

    public static final int R=3;

    public static final int C=3;

    // matrix for tracking purpose 

    public static boolean [][] visited;

    

    //input matrix

    public static char [][] mat ={ {'a','c','d'},{ 'h','b','a'},{ 'i','g','f'}};

    

    // just storing all 8 position for iterative recurs 

    public static int [] x = {1,0,1,1,-1,-1,0,-1};

    public static int [] y = {0,1,1,-1,1,-1,-1,0};

    

    //dp storage

    public static int [][]dp;

    

    public static int max(int a, int b)

    {

        return(a>b?a:b);

    } 

    //will check if and i,j pair in matrix valid or not

    public static boolean isValid(int i, int j)

    {

        if(i<0 || j<0 || i>=R || j >=C)

            return false;

        else

            return true;

    }

    

    public static int getpath_util(char m, int r, int c)

    {

        if(!isValid(r,c) || visited[r][c] ||  m+1 != mat[r][c])

            return 0;

        if(dp[r][c]!= -1)

        {

            return dp[r][c];

        }

        

        // make this visited so in subsequent call it will not be taken into account

        

        visited[r][c] = true;

        int ans=0;

        for(int k=0; k<8; k++)

        {

            ans= max(ans, 1+getpath_util(mat[r][c], x[k]+r, y[k]+c));

        }  

        

        // unset this

        visited [r][c] = false;

        

        return dp[r][c] = ans;

        

    }

    public static void getpath(char m)

    {

        int ans=0;

        for(int i=0; i<R; i++)

        {

            for(int k=0; k<C;k++)

            {

                if(mat[i][k] == m)

                {

                    for(int j=0; j<8; j++)

                    {   

                        ans = max(ans, 1+getpath_util(m, i+x[j], k+y[j]));

                    }       

                }

            }

        }   

        System.out.println(ans);

    }

    public static void main(String[]args)

    { 

        visited  = new boolean[R][C];

        dp = new int [R][C];

        for(int i=0; i<R;i++)

            for(int k=0; k<C; k++)

                dp[i][k]=-1;

        for(int i=0; i<R;i++)

            for(int k=0; k<C; k++)

                visited[i][k]=false;

        getpath('a');

        getpath('e');

        getpath('b');

        getpath('f'); 

    }

}

Source:- gfg

Merge two sorted linked list (Recursive Approach)

Merge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code

Node *Merge(Node * head1, Node *head2)
{
        // Base conditions

       if(! head1 || !head2)
       {
              if(!head1)
                   return head2;
              else
                   return head1;
     
        }
        else
        {

                 if(Node1.data <= Node2.data)
                 {

                        Node1.next = Merge(Node1.next, Node2)
                        return Node1;

                 }
                 else
                 {
       
                       Node2.next= Merge(Node1, Node2.next);
                       return Node2;
                 }
        }

}

[Uber][LeetCode] Trapping Rain Water

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Input: height = [4,2,0,3,2,5]
Output: 9

Approach: Basically if we see the problem closely, we can easily figure out that the trapped water amount at any bar 'i' is as follows:

water(i) = Min (max height among all the bar in left of i, max height among all the bars in right of i ) - height(i)

We just need the sum of all of these amount to get the answer. We can achieve it using brute force approach but let's try to do better:

we can pre calculate the max height from left for every i and store in an array say leftMax and we can do the same from the right and store it in the array say rightMax. Now the calculation is something like this:

• FOR i = 1 TO n
• water += ( Min(leftMax[i], rightMax[i]) - height[i])

This approach will solve the problem in linear time but if you see it is taking extra space. Let's try to reduce it. The intuition is if till leftMax is greater than rightMax, we just calculate according to rightMax only right? (see above, we take the min only). Same thing we can say about when rightMax is greater than leftMax.

Now we can use two pointer approach one from left (index = 0) and one from right(index = n - 1) and can follow the following steps:

• WHILE left < right
• IF height[left] < height[right]
• IF height[left] > leftMax //. can't trap water 
• leftMax = height[left]
• ELSE
• water += leftMax - height[left]
• ++left;
• ELSE
• // same for right
• --right

Implementation in C#:

Approach 1:

    public int Trap(int[] height) 

    {

        int length = height?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int[] leftMax = new int[length];

        leftMax[0] = height[0];

        for (int i = 1; i < length; ++i)

        {

            leftMax[i] = Math.Max(leftMax[i - 1], height[i]);

        }

        int[] rightMax = new int[length];

        rightMax[length - 1] = height[length - 1];

        for (int i = length - 2; i >=0; --i)

        {

            rightMax[i] = Math.Max(rightMax[i + 1], height[i]);

        }

        int sum = 0;

        for (int i = 1; i < length - 1; ++i)

        {

            sum += (Math.Min(leftMax[i], rightMax[i]) - height[i]);

        }

        return sum;

    }

Approach 2:

    public int Trap(int[] height)

    {

        int length = height?.Length ?? 0;

        if (length <= 2)

        {

            return 0;

        }

        int water = 0;

        int leftMax = 0, rightMax = 0;

        int left = 0, right = length - 1;

        while (left < right)

        {

            if (height[left] < height[right])

            {

                if (height[left] <= leftMax)

                {

                    water += leftMax - height[left];

                }

                else

                {

                    leftMax = height[left];

                }

                ++left;

            }

            else

            {

                if (height[right] <= rightMax)

                {

                    water += rightMax - height[right];

                }

                else

                {

                    rightMax = height[right];

                }

                --right;

            }

        }

        return water;

    }

Complexity: O(n)

Insertion Sort

The idea behind the insertion sort is to loop over positions in the array, starting with index 1. Each element at the given index needs to be inserted  into the correct place in the array.

Although it is one of the elementary sorting algorithms with O(n²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

Implementation:

void insertionSort(int *arr, int len)
{
if(arr == NULL || len <= 1)
return;

for(int i = 1; i < len; ++i)
{
int key = arr[i];
int j = i  - 1;
for(; j >= 0 && arr[j] > key; --j)
arr[j+1] = arr[j];

arr[j + 1] = key;
}
}

Complexity: O(n²)

Size of binary tree

Problem: Write a method which returns the number of nodes present in the given binary tree.

Solution: Do any traversal and instead of printing the node, count the number of nodes. I am using post order traversal here.

Implementation:

//Public Interface

int BSTree::size()

{

if(!root)

return 0;

return size(root);

}

//Actual Implementation

int BSTree::size(BSTree::Node *node)

{

if(!node)

return 0;

int ls = size(node->left);

int rs = size(node->right);

return ls + rs + 1;

} 

Complexity: O(n)

Longest Increasing Subsequence

A sequence of numbers a₁, a₂,..., a_n, a sub-sequence is a_i1, a_i2, ... , a_ik where 1 <= i₁ < i₂ < ... < i_k <= n and an increasing sub-sequence is one in which the numbers are getting strictly larger. The task is to find the increasing sub-sequence of greatest length.

Example: The longest increasing sub-sequence of 5, 2, 8, 6, 3, 6, 9, 7 is 2, 3, 6, 9:

Solution: Create a graph of all permissible transitions: establish a node i for each element ai, and add directed edges (i, j) whenever it is possible for a_i and a_j to be consecutive elements in an increasing sub-sequence,that is, whenever i < j and a_i < a_j.

Note that this graph G = (V,E) is a dag, since all edges (i, j) have i < j, and there is a one-to-one correspondence between increasing sub-sequences and paths in this dag. Therefore, our goal is simply to find the longest path in the dag. Here is the algorithm:

Implementation:

int LIS(int arr[], int len)
{
int *L = new int[len];

for(int i = 0; i < len; ++i)
L[i] = 1;

for(int j = 1; j < len; ++j)
{
for(int i = 0; i < j; ++i)
{
if((arr[j] > arr[i]) && (L[j] < L[i] + 1))
L[j] = L[i] + 1;
}
}

int max = 0;
for(int i = 0; i < len; ++i)
{
if(max < L[i])
max = L[i];
}

delete [] L;
return max;
}

Complexity: O(n²)

OLA Question: Modify Boolean matrix

Problem: Given a Boolean matrix , modify it such that if a matrix cell mat[i][j] is true then make all the cells of i^th row and j^th column as true.

Solution: Following are the steps -

1. Traverse the first row and set a variable firstRowFlag to indicate whether all the cells in first row should be set to true or not.
2. Similarly traverse the first column and set a variable firstColFlag to indicate whether all the cells in first column should be set to true or not.
3. Now set all the cells in first row and column as false.
4. Traverse the input matrix and see if mat[i][j] is true, then set mat[0][j] and mat[i][0] as true.
5. Traverse the input matrix and for each entry mat[i][j], check if either mat[0][j] or mat[i][0] is true, then set mat[i][j] to true.
6. Now, using firstRowFlag and firstColFlag, update first row and first column if needed.

Implementation:

void modifyBoolMatrix(bool **mat, int M, int N)

{

bool firstRowFlag = false, firstColFlag = false;

for(int i = 0; i < N; ++i)

{

if(mat[0][i])

{

mat[0][i] = false;

firstRowFlag = true;

}

}

for(int i = 0; i < M; ++i)

{

if(mat[i][0])

{

mat[i][0] = false;

firstColFlag = true;

}

}

for(int i = 1; i < M; ++i)

{

for(int j = 1; j < N; ++j)

{

if(mat[i][j])

{

mat[0][j] = true;

mat[i][0] = true;

}

}

}

for(int i = 1; i < M; ++i)

{

for(int j = 1; j < N; ++j)

{

if(mat[0][j] || mat[i][0])

mat[i][j] = true;

}

}

if(firstRowFlag)

{

for(int i = 0; i < N; ++i)

mat[0][i] = true;

}

if(firstColFlag)

{

for(int i = 0; i < M; ++i)

mat[i][0] = true;

}

}

Complexity: O(M * N)