LIS of length K

LIS of length K

  July 05, 2018    

---

problem:
Find LONGEST INCREASING Subsequence of length k

idea is to use dynamic programming.
Q: When will length k LIS formed
Ans : array having LIS of length k-1 at index j and curr index (>j) having higher element.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class lisLenK
 {
  public static int fn(int a[],int n,int k)
  {
      int lis[][]=new int[n][k+1];
      int res=-1;
      for(int i=0;i<n;++i)
      {
          lis[i][1]=a[i];
          for(int j=0;j<i;++j)
          {
              if(a[j]<a[i])
              {
                  for(int t=k;t>1;--t)
                  {
                      if(lis[j][t-1]!=0)
                      {
                          lis[i][t]=Math.max(lis[i][t],lis[j][t-1]+a[i]);
                      }
                  }
              }
          }
          res=Math.max(res,lis[i][k]);
      }
       /*for(int i=0;i<n;++i)
      {
          for(int j=0;j<=k;++j)
          System.out.print(lis[i][j]+" ");
          System.out.println();}*/
      return (res>0)?res:-1;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int k=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n,k));
}
}
}

Read More

Transform String by moving character

Transform String by moving character

  June 29, 2018    

---

Problem:
transform string A into string B in minimum number of steps. Only one operation is allowed, chose any of the characters in string A and place it in the front of A


Idea is to first check if all the characters in both strings are same or not.
Then check the matching sequence from right to left (String B to A)
Those characters who doesn't have same sequence will be moved to front.



Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class transformStringbyMovingChartoFront
 {
  public static int fn(char a[],char []b)
  {
      if(a.length!=b.length) return -1;
      Map<Character,Integer> map=new HashMap<>();
      for(int i=0;i<a.length;++i)
      {
          if(map.containsKey(a[i]))
          map.put(a[i],map.get(a[i])+1);
          else
          map.put(a[i],1);
      }
       for(int i=0;i<b.length;++i)
      {
          if(!map.containsKey(b[i]) || map.get(b[i])==0)
          return -1;
          map.put(b[i],map.get(b[i])-1);
      }
      int j=a.length-1;
      int i=b.length-1;
      int c=0;
      for(;i>=0 && j>=0;)
      {
          if(b[i]==a[j])
          {
              --i;
              --j;
              ++c;
          }
          else
          --j;
      }
      return a.length-c;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=Integer.parseInt(ab.nextLine());
while(t-->0)
{
    String a[]=ab.nextLine().split(" ");
   /* for(int i=0;i<a.length;++i)
    System.out.print(a[i]);*/
    if(a.length==1)
    System.out.println(fn(a[0].toCharArray(),ab.next().toCharArray()));
    else
    System.out.println(fn(a[0].toCharArray(),a[1].toCharArray()));
}
}
}

Read More

Max sum path in two Array

Max sum path in two Array

  June 28, 2018    

---

Problem:

Given two sorted arrays such the arrays may have some common elements.
Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can start from any array and switch from one array to another array only at common elements.

Input:

1
5 5
1 2 3 4 5
5 6 7 8 9 

Output
45

Explanation:

1+2+3+4+5+6+7+8+9=45

Intuition:

If we look closer to the problem , it is like merge sort merge Function.
We have to maintain 2 variables for sum of both array.
When we are having common element we can choose any sum and again follow process.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class maxSumpathTwoArray
 {
  public static int fn(int a[],int b[],int n,int m)
  {
    int sum1=0,sum2=0;
    int res=0,i=0,j=0;
    while(i<n && j<m)
    {
      if(a[i]==b[j])
      {
        res+=Math.max(sum1,sum2)+a[i];
        sum1=sum2=0;
        ++i;
        ++j;
      }
      else if(a[i]<b[j])
      sum1+=a[i++];
      else
      sum2+=b[j++];
    }
    while(i<n)
    sum1+=a[i++];

    while(j<m)
    sum2+=b[j++];
    return res+Math.max(sum1,sum2);
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int m=ab.nextInt();
    int arr[]=new int[n];
    int arr2[]=new int[m];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    for(int i=0;i<m;++i)
    arr2[i]=ab.nextInt();
    System.out.println(fn(arr,arr2,n,m));
}
}
}

Read More

Search Element in Sorted and rotated Array

Search Element in Sorted and rotated Array

  June 21, 2018    

---

One of the approach will be to find rotation point and check if number is in left or right subarray , Apply Binary Search for that part.
This will take two scan of Array

In one scan we can also perform same:

Algo:
check if mid is element to be searched , if so return mid;
else one of the subarray either from left to mid OR mid to right will be sorted 
Check for sorted Array and range of number i.e. whether number lies in which range and change accordingly


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class searchSortedRotated
 {
   public static int bSearch(int a[],int x,int n)
   {
      int l=0,r=n-1;
      while(l<=r)
      {
        int mid=(l+r)>>1;
        if(a[mid]==x)
        return mid;
      //atlest one of the subarray will be sorted so check if number ranges in sorted or not
      if(a[l]<=a[mid])
      {
        if(x>=a[l] && x<a[mid])
        r=mid-1;
        else
        l=mid+1;
      }
      else //if(a[mid]>=a[r])
      {
        if(x>a[mid] && x<=a[r])
        l=mid+1;
        else
        r=mid-1;
      }
      }
      return -1;
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    int k=ab.nextInt();
    System.out.println(bSearch(arr,k,n));
}
}
}

Read More

Check if TicTacToe is valid

Check if TicTacToe is valid

  June 17, 2018    

---

Problem :
A Tic-Tac-Toe board is given after some moves are played. Find out if the given board is valid, i.e., is it possible to reach this board position after some moves or not.
X will be move first

https://practice.geeksforgeeks.org/problems/tic-tac-toe/0

here we are having few cases :

IF x count==o it means o should win and if x wins then it will be invalid.
IF x count==o+1 it means x will win , in that case if o wins then it will be invalid 
IF xcount-o count !=1 || 0 it means invalid
Else valid 

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class validTicToe
 {
   public static boolean wins(char a[],char t)
   {
     int win[][] = {{0, 1, 2}, // Check first row.
                 {3, 4, 5}, // Check second Row
                 {6, 7, 8}, // Check third Row
                 {0, 3, 6}, // Check first column
                 {1, 4, 7}, // Check second Column
                 {2, 5, 8}, // Check third Column
                 {0, 4, 8}, // Check first Diagonal
                 {2, 4, 6}}; // Check second Diagonal
                 for(int i=0;i<8;++i)
                 {
                   if(a[win[i][0]]==t && a[win[i][1]]==t && a[win[i][2]]==t)
                   return true;
                 }
                 return false;
   }
  public static boolean isValid(char a[])
  {
    int o=0,x=0;
    for(int i=0;i<9;++i)
    {
      if(a[i]=='X')
      ++x;
      else
      ++o;
    }
    if(x==o)
    {
      //System.out.println("eq");
      if(wins(a,'X'))
      return false;
    }
    else if(x==o+1)
    {
    //  System.out.println("x>");
      if(wins(a,'O'))
      return false;
      return true;
    }
    return false;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    char arr[]=new char[9];
    for(int i=0;i<9;++i)
    arr[i]=ab.next().charAt(0);
    System.out.println(isValid(arr));
}
}
}

Read More

Three Way Partitioning QuickSort

Three Way Partitioning QuickSort

  June 17, 2018    

---

In general , we pick an element as pivot and peform partitioning .
Now as per 3 way partitioning we will choose a range to perform partition.

Problem:
https://practice.geeksforgeeks.org/problems/three-way-partitioning/1

Here we are not bothered about the sequence we only care about left element should be less than range and right elements greater than .

So we choose two pointers 
1:start to replace less element
2: end to replace greater element

But we are not incrementing i every time as we  don't know that after swap element is at right position or not as if we swap larger element with last positioned end ,it might happen that that element can be less or greater then again recheck need to be done..

Code:


public ArrayList<Integer> threeWayPartition(ArrayList<Integer> a, int x, int y)
{
        int l=0,r=a.size()-1;
        int i=0;
        while(i<=r)
        {
            if(a.get(i)<x)
            {
                int temp=a.get(l);
                a.set(l,a.get(i));
                a.set(i,temp);
                ++l;
                ++i;
            }
            else if(a.get(i)>y)
            {
                 int temp=a.get(r);
                a.set(r,a.get(i));
                a.set(i,temp);
                --r;
            }
            else
            ++i;
          //  System.out.println(a);    
        }
       // System.out.println(a);
        return a;
        }

Read More

max of all min for every window size

max of all min for every window size

  May 25, 2018    

---

Problem:
for every window size you have to find maximum value 

idea is to find previous smaller and next smaller element 
this element is minimum for nextSmaller[i]-prevSmaller[i]-1 
Find all maximum


Code will comment:

import java.util.*;
import java.lang.*;
import java.io.*;
class maxofMinForEverywindow
 {
   public static void prevSmallerIndex(int a[],int j[],int n)
   {
     Stack<Integer> s=new Stack<Integer>();
     s.push(n-1);
     for(int i=n-2;i>=0;--i)
     {
       while(!s.isEmpty() && a[s.peek()]>a[i])
       {
         int k=s.pop();
         j[k]=i;
       }
          s.push(i);
     }
     while(!s.isEmpty())
     {
       int k=s.pop();
       j[k]=-1;
     }
   }
   public static void nextSmallerIndex(int a[],int j[],int n)
   {
     Stack<Integer> s=new Stack<Integer>();
     s.push(0);
     for(int i=1;i<n;i++)
     {
         while(!s.isEmpty() && a[s.peek()]>a[i])
         {
           int k=s.pop();
           j[k]=i;
         }
            s.push(i);
     }
     while(!s.isEmpty())
     {
       int k=s.pop();
       j[k]=n;
     }
   }
  public static void fn(int a[],int n)
  {
    int nextSmaller[]=new int[n];
    int prevSmaller[]=new int[n];
    nextSmallerIndex(a,nextSmaller,n);
    prevSmallerIndex(a,prevSmaller,n);
    /*
    for(int x:prevSmaller)
    System.out.print(x+" "); */
    //Now we know that a[i] is minimum in window from prevSmaller to nextSmaller
    //find max for the same size of window and store them in array
    int res[]=new int[n+1]; // it holds max of min value for window size n
    for(int i=0;i<n;++i)
    {
      int t=nextSmaller[i]-prevSmaller[i]-1;
     res[t]=Math.max(res[t],a[i]);
    }
    // now we will be having result but some values are missing
    //as per observation res[i] will be greater than or equal to res[i+1..n]
    //fill values
    for(int i=n-1;i>=1;--i)
    {
      res[i]=Math.max(res[i],res[i+1]);
    }
    for(int i=1;i<=n;++i)
    System.out.print(res[i]+" ");
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
      fn(arr,n);
    System.out.println();
}
}
}

Read More

Infix to postfix implementation

Infix to postfix implementation

  May 25, 2018    

---

Idea is to print operand and push operand to stack
If current operator having priority greater than stack top operator then push
else remove operator till operator's precedence is low

if ) is detected pop from stack until ( is detected.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class infixtopost
 {
      static int prec(char ch)
    {
        switch (ch)
        {
        case '+':
        case '-':
            return 1;

        case '*':
        case '/':
            return 2;

        case '^':
            return 3;
        }
        return -1;
    }
  public static void infixToPostFix (char a[])
  {
      Stack<Character> s=new Stack<Character>();
      for(int i=0;i<a.length;++i)
      {
          //if(a[i])
          if(prec(a[i])==-1 && a[i]!=')' && a[i]!='(')
          System.out.print(a[i]);
          else
          {
             if(a[i]=='(')
             s.push(a[i]);
            else if(a[i]==')')
             {
                 while(!s.isEmpty() && s.peek()!='(')
                 {
                     System.out.print(s.pop());
                 }
                 if(!s.isEmpty() && s.peek()=='(')
                 s.pop();
             }
             else{
             while(!s.isEmpty() && prec(s.peek())>=prec(a[i]))
             {
                  System.out.print(s.pop());
             }
             s.push(a[i]);}
          }
      }
      while(!s.isEmpty())
              System.out.print(s.pop());
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    infixToPostFix(ab.next().toCharArray());
    System.out.println();
}
}
}

Read More

Longest Common Increasing Subsequence (LCS + LIS)

Longest Common Increasing Subsequence (LCS + LIS)

  May 20, 2018    

---

Here one approach is to Find LCS then follow up with LIS

Else 
we can do it in 1 time

Issue faced:

how to maintain previous count i.e. how to know the number of increasing subsequence for current matched element.

Here we are initiating that with 0 and whenever a match found we put table[i]=current+1
Whenever we got to know that element of arr2[] > arr1[] and table[i] has element > current it means till i we got table[i] increasing subsequence.
Hence change current value.

and if we got match for the same arr1[] element then it will be having value 1 more than previous
if not found then neglect current and start again

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class longestCommonIncreasingSubsequence
 {
  public static int LCIS(int a[],int b[],int n,int m)
  {
    int ans=0;
    int res[]=new int[m];
    for(int i=0;i<n;++i)
    {
      //for every same element LIS is 1 (0+1)
      int c=0;
      for(int j=0;j<m;++j)
      {
        if(a[i]==b[j])
        res[j]=Math.max(res[j],c+1);
        // if a[i] is greater than b[j] and we already has LCIS >c then update
        if(a[i]>b[j])
        c=Math.max(c,res[j]);
        ans=Math.max(ans,res[j]);
      }
    }
    return ans;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    int m=ab.nextInt();
    int arr2[]=new int[m];
    for(int i=0;i<m;++i)
    arr2[i]=ab.nextInt();
    System.out.println(LCIS(arr,arr2,n,m));
}
}
}

Read More

Check if strings are rotations of each other or not

Check if strings are rotations of each other or not

  May 17, 2018    

---

Earlier the approach was discussed in this post which handles substring match as pattern

Here i am going to use KMP algorithm’s lps construction which will help me to longest match which is prefix of string b and suffix of string a.
By which we will know the rotating point .
From this point match the characters.

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

class stringrotationofeachother

 {

  public static boolean isRotation(String a,String b)

  {

    int n=a.length();

    int m=b.length();

    if(n!=m)

    return false;

    int lps[]=new int[n];

    int i=1,len=0;

    lps[0]=0;

    while(i<n)

    {

      if(a.charAt(i)==b.charAt(len))

      {

        lps[i]=++len;

        ++i;

      }

      else

      {

        if(len==0)

        {

          lps[i]=0;

          ++i;

        }

        else

        {

          len=lps[len-1];

        }

      }

    }

  //  System.out.println(lps[n-1]);

  i=0;

    for(int k=lps[n-1];k<m;++k)

    {

      if(b.charAt(k)!=a.charAt(i++))

      return false;

    }

    return true;

  }

public static void main (String[] args)

{

Scanner ab=new Scanner(System.in);

int t=ab.nextInt();

while(t-->0)

{

    System.out.println(isRotation(ab.next(),ab.next())?"1":"0");

}

}

}

Read More

Two numbers with sum closest to zero

Two numbers with sum closest to zero

  May 01, 2018    

---

Sort array
Run a loop with start=0 and end =n-1 , add both numbers and look for minimum sum absolute value.


import java.util.*;
import java.lang.*;
import java.io.*;
class sumClosestToZero
 {
   public static void closestNumber(int arr[],int n)
   {
     Arrays.sort(arr);
     int a=arr[0],b=arr[n-1];
     int min=Integer.MAX_VALUE;
     int l=0,r=n-1;
     while(l<r)
     {
       int sum=arr[l]+arr[r];
       if(Math.abs(sum)<min)
       {
         min=Math.abs(sum);
         a=arr[l];
         b=arr[r];
       }
       if(sum<0)
       ++l;
       else
       --r;
     }
     System.out.print(a+" "+b);
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
      closestNumber(arr,n);
    System.out.println();
}
}
}

Read More

add two Binary Strings

add two Binary Strings

  April 30, 2018    

---

First make their length equal by appending 0 at start
then perform addition


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class binaryAddition
 {
   public static StringBuffer addZero(StringBuffer a,int len)
   {
     String str=new String();
     while(len-->0)
     {
       str+='0';
     }
     a.insert(0,str);
     return a;
   }
   public static StringBuffer addBinary(StringBuffer a,StringBuffer b)
   {
     if(a.length()<b.length())
     {
       a=addZero(a,b.length()-a.length());
     }
     if(b.length()<a.length())
     b=addZero(b,a.length()-b.length());
     //System.out.println(a);
     //System.out.println(b);
     //now add binary strings
     StringBuffer res=new StringBuffer();
     int carry=0;
     for(int i=a.length()-1;i>=0;--i)
     {
       res.append(String.valueOf((carry+a.charAt(i)+b.charAt(i)-'0'-'0')%2));
       carry=(carry+a.charAt(i)+b.charAt(i)-'0'-'0')/2;
    //   System.out.println("carry "+carry);
     }
     if(carry==1)
     res.append('1');
     return res.reverse();
   }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    System.out.println(addBinary(new StringBuffer(ab.next()),new StringBuffer(ab.next())));
}
}
}

Read More

Max sum path in two arrays

Max sum path in two arrays

  March 29, 2018    

---

Problem:

Given two arrays(sorted)
The function returns the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays.
Switch (one array to another )from common elements

Reference:
https://practice.geeksforgeeks.org/problems/max-sum-path-in-two-arrays/1




Idea is to use merge sort algorithm and maintain two sum for 1st and 2nd array.
When common element is found then we will add max sum from both the arrays to result.

   int maxPathSum(int ar1[], int ar2[])
   {
       int i,j,sum,isum,jsum;
       i=j=sum=isum=jsum=0;
       while(i<ar1.length && j<ar2.length)
       {
         if(ar1[i]==ar2[j])
         {
           sum+=Math.max(isum,jsum)+ar1[i];
           isum=jsum=0;
           ++i;++j;
         }
         else if(ar1[i]<ar2[j])
         {
           isum+=ar1[i++];
         }
         else
         jsum+=ar2[j++];
       }
       while(i<ar1.length)
       {
         isum+=ar1[i++];
       }
       while(j<ar2.length)
       {
         jsum+=ar2[j++];
       }
       return sum+Math.max(isum,jsum);
   }

Read More