Largest subarray of 0's and 1's

Largest subarray of 0's and 1's

  June 16, 2018    

---

Problem
Given an array of 0's and 1's , give  size of  the  largest sub array with equal number of 0's and 1's .

Idea to change array to -1 and 1 and now problem changes to maximum subarray having sum 0.
Use a map to store least index for every sum and when we encounter same sum again it means that from that index (stored in map) to i (current) we have a subarray with sum 0.

Code

void manipulate(int a[])
    {
        for(int i=0;i<a.length;++i)
        {
            if(a[i]==0)
            a[i]=-1;
        }
    }
    int maxLen(int[] a)
    {
        manipulate(a);
         Map<Integer,Integer> m=new HashMap<>();
         int maxLen=0;
         int cursum=0;
         for(int i=0;i<a.length;++i)
         {
             cursum+=a[i];
             if(m.containsKey(cursum))
             {
                 maxLen=Math.max(maxLen,i-m.get(cursum));
             }
             else if(cursum==0)
             maxLen=i+1;
             else
             m.put(cursum,i);
         }
        // System.out.print(m+" "+cursum);
         return maxLen;
    }

Read More

Preorder to Postorder

Preorder to Postorder

  May 25, 2018    

---

Idea is to find starting position of right node of tree i.e. next greater element
Recur for rightSubtree
Recur for left subtree

base condition : when only one node

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class preorderPost
 {
    static int in=0;
    static boolean flag=false;
    //check if it is valid representation of preorder
    //if so then all nodes ahead a[j] must be greater than a[l] 
    public static boolean checkIncreasing(int a[],int l,int j,int n)
    {
        for(int i=j+1;i<=n;++i)
        if(a[i]<a[l])
        {
            flag=true;
            return true;
        }
        return false;
    }
  public static void pre2post(int a[],int l,int r,int p[])
  {
      if(l>r) return;
    if(l==r){ p[in++]=a[l];
    return;}
    int j=l+1;
    for(;j<=r;++j)
    if(a[j]>a[l])
    break;
    if(checkIncreasing(a,l,j,r))
    return;
    pre2post(a,l+1,j-1,p);
    pre2post(a,j,r,p);
    p[in++]=a[l];
    return ;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    in=0;
    flag=false;
    int n=ab.nextInt();
    int arr[]=new int[n];
    int post[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
     // Integer in=new Integer(0);
      pre2post(arr,0,n-1,post);
      if(flag)
      System.out.print("NO");
      else{
      for(int x:post)
    System.out.print(x+" ");}
    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

Lowest Common Ancestor in BST

Lowest Common Ancestor in BST

  April 28, 2018    

---

Lowest Common Ancestor is parent of both node or node itself.

we have following cases:

1: either node is equal to one of argument 
Then it will be LCA

2 : if one node lies in left one in and right child
Then it will be LCA


Code:

 Node LCA(Node node,int min,int max)
    {
        if(node==null)
        return null;
        if((node.data>=min && node.data<=max))
        return node;
        if(node.data<min && node.data<max)
        return LCA(node.right,min,max);
        return LCA(node.left,min,max);
    }
    Node lca(Node node, int n1, int n2) 
    {
        int min=Math.min(n1,n2);
        int max=Math.max(n2,n1);
        return LCA(node,min,max);
    }

Read More

Unsorted Array Geeks Solution

Unsorted Array Geeks Solution

  March 20, 2018    

---

First Element having position same as its sorted array
i.e. 
The position of first element such that all left elements are less and right elements are greater.

Approach 1:
Sort array and check if sorted array and given array have same element value then return that
This will take O(nlogn)

Approach 2:
 Store min element from right hand side and max from left hand side and check when element is greater than left hand max ans right hand min value.



public static int starElement(int arr[],int n)
{
int res=-1;
// hold minimum value from right to current element
int Rmax[]=new int[n];
Rmax[n-1]=arr[n-1];
for(int i=n-2;i>0;--i)
{
Rmax[i]=Math.min(Rmax[i+1],arr[i]);
}
//lmax will hold max from 0 to i-1th element
int lmax=arr[0];
for(int i=1;i<n-1;++i)
{
if(arr[i]>=lmax && arr[i]<=Rmax[i+1])
return arr[i];
// System.out.println("Element is "+arr[i]+" left max "+lmax+" rmax "+Rmax[i]);
lmax=Math.max(lmax,arr[i]);
}
return -1;
}
}

Read More

Maximize no of 1 by flipping k 0

Maximize no of 1 by flipping k 0

  March 20, 2018    

---

Idea is to sliding window concept.
For first k 0's increase right window index.

When we already have gone through k 0's then increase left window index to first occurrence of 0 from leftwindow index.


     public static int max1(int arr[],int n,int k)
     {
         int i=0;
         int max=0;
         int startindex=0;
         while(i<n)
         {
             if(arr[i]==0){
//decrement count of bits that can be changed
             if(k>0)
             {
                 --k;
             }
else
{
while(startindex<=i && arr[startindex++]!=0);
 
}
}
++i;
max=Math.max(max,i-startindex);
         }
return max;
}


Another approach with same concept
https://www.careercup.com/question?id=5106425965576192
}

Read More

Even and odd elements at even and odd positions

Even and odd elements at even and odd positions

  January 31, 2018    

---

Approach 1:
Maintain 2 arrays
1 for even and another for odd and print them.
O(n) time and Space

Code:

     public static void evenOddpos(int arr[],int n)
{
List<Integer> even=new ArrayList<Integer>();
List<Integer> odd=new ArrayList<Integer>();
for(int x:arr)
{
if((x&1)==1)
{
odd.add(x);
}
else
even.add(x);
}
int i=0,j=0;
int s=even.size(),s2=odd.size();
while(i<s && j<s2)
{
System.out.print(even.get(i++)+" ");
System.out.print(odd.get(j++)+" ");
}
while(i<s)
System.out.print(even.get(i++)+" "); 
while(j<s2)
System.out.print(odd.get(j++)+" ");
}
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();
evenOddpos(arr,n);
    System.out.println();
}
}



Approach 2:

Maintain 2 pointers and look for even/odd element and print them
O(n) time and O(1) Space

Code:

public static int getelement(int arr[],int pos,boolean flag,int n)
{
if(flag)
{
while(pos<n && (arr[pos]&1)==1)
{
++pos;
}
}
else{
  while(pos<n && (arr[pos]&1)==0)
{
++pos;
}
}
return pos;
}
     public static void evenOddpos(int arr[],int n)
{
int epos=0,opos=0;//even odd position pointer
boolean i=true;
while(epos<n && opos<n)
{
if(i)
{
epos=getelement(arr,epos,true,n);
if(epos<n)
System.out.print(arr[epos++]+" "); 
}
else
{
opos=getelement(arr,opos,false,n);
if(opos<n)
System.out.print(arr[opos++]+" "); 
}
i=!i;
}
// System.out.println("\n odd pos : "+opos+" even pos "+epos);
while(epos<n)
    if((arr[epos++]&1)==0)
{System.out.print(arr[--epos]+" ");
     ++epos;
} 
while(opos<n)
if((arr[opos++]&1)==1)
{System.out.print(arr[--opos]+" ");
     ++opos;
}
}
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();
evenOddpos(arr,n);
    System.out.println();
}
}

Read More