Find Length of longest substring without repeating characters in O(n). eg if string is "HELLOWORLD" then output is "WORLD" len = 5

#include<iostream.h>
#include<conio.h>
#include<string.h>

int nrcs(char *str)
{
    int n = strlen(str);
    int scan[256];
    for(int i =0; i<256 ;i++)
            scan[i]=-1;
   
    int curLen=1, maxLen=1, prev;
    scan[str[0]]=-1;
   
    int start=0,s=0,end=n-1,e;
   
    for(int i=1; i<n ;i++)
    {
            prev = scan[str[i]];
            if( prev ==-1 || i - curLen > prev)
                curLen++;
            else
            {
                    start=s;
                    end =e;
                    s = prev+1;
                    e=s;
                   
                    if(curLen > maxLen)
                    {
                           maxLen = curLen;
                    }
                    curLen = i - prev;
            }
            scan[str[i]]=i;
            e=i;
    }
    if(curLen > maxLen)
                       maxLen = curLen;
    if(e-s  >end - start)
    {
               start=s;
               end=e;
    }
    for(int j = start; j<= end ; j++)
            cout<<"\n"<<j-start+1<<" "<<str[j];
    return maxLen;
}

int main()
{
    char *str = "helloworld";
    cout<<"\n\nlen is "<<nrcs(str);
    getch();
}

Initialise an array in spiral form (inside out).

/*

Initialise the center element of the matrix with 1 and then assign all other cells in spiral order.
21 22 23 24 25
26  7   8   9  10
19  6   1   2  11
18  5   4   3  12
17 16 15 14 13

*/

// this will work only for odd number of rows and columns square matrix as in even rows and columns square //matrix there is no center element.

#include<iostream.h>

#include<conio.h>

const int rowcol=5;

int matrix[rowcol][rowcol];

void spiralinvert(int row,int col)

{

     int count=2;

     int cstart=col/2,cend=cstart+1;

     int rstart=row/2,rend=rstart+1;

     int n=row*col;

     matrix[cstart][rstart]=1;

     cout<<"spiral starts"<<endl;

     while(1)

     {

                   

                   for(int i=cstart+1;i<=cend;i++,count++)

                           matrix[rstart][i]=count;

                   cstart--;

                   if(count>=n)

                               break;

                   for(int j=rstart+1;j<=rend;j++,count++)

                                   matrix[j][cend]=count;

                   rstart--;

                   if(count>=n)

                               break;

                   for(int k=cend-1;k>=cstart;k--,count++)

                           matrix[rend][k]=count;

                   cend++;

                   if(count>=n)

                      break;

                   for(int l=rend-1;l>=rstart;l--,count++)

                           matrix[l][cstart]=count;

                   rend++;

                   if(count>=n)

                            break;

     }

     cout<<"spiral ends"<<endl;

}

void display(int row,int col)

{

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

     {

             cout<<"\n";

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

                     cout<<"\t"<<matrix[i][j];

     }

}

int main()

{

    spiralinvert(rowcol,rowcol);

    display(rowcol,rowcol);

    getch();

    return 0;

}

Print 2D array in spiral form.

/*

if array is 

1    2   3   4   5

6    7   8   9  10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

output:- 1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13

*/

#include<iostream.h>

#include<conio.h>

int matrix[5][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};

void spiralprint(int row,int col)

{

     int cstart=0,cend=col-1,rstart=0,rend=row-1,n=col*row;

     int count=0;

     while(count<n)

     {

                   for(int i=cstart;i<=cend;i++,count++)

                           cout<<"  "<<matrix[rstart][i];

                   rstart++;

                   for(int j=rstart;j<=rend;j++,count++)

                           cout<<"  "<<matrix[j][cend];

                   cend--;

                   for(int k=cend;k>=cstart;k--,count++)

                           cout<<"  "<<matrix[rend][k];

                   rend--;

                   for(int l=rend;l>=rstart;l--,count++)

                           cout<<"  "<<matrix[l][cstart];

                   cstart++;

     }

                   

}

int main()

{

    spiralprint(5,5);

    getch();

    return 0;

}

SUDOKU SOLVER

/*

• move from left to right and top to down.
• In the empty cell try 1 to 9 and chose the first one that fit i.e chosen no. should not conflict with any entry in the same row and column.
• In a 9x9 sudoku there are 9 small(3x3) matrix, the chosen number should be unique in this smaller(3x3) matrix.
• Now move on to next cell and repeat the same procedure.
• If no number fits in this cell then backtrack(return false) to the previous made decision and change it to next higher value that fit.
• If no value fits in this cell backtrack to next higher level.

*/

#include<iostream.h>

#include<conio.h>

int sudoku[9][9]={{0,0,4,3,0,2,1,0,0},{0,6,0,0,0,0,0,2,0},{9,0,0,0,0,0,0,0,7},

                  {0,0,1,0,3,0,2,0,0},{2,0,0,9,0,6,0,0,1},{0,0,9,0,5,0,4,0,0},

                  {7,0,0,0,0,0,0,0,3},{0,1,0,0,0,0,0,4,0},{0,0,8,5,0,3,9,0,0}};

                 

bool findunassignedcell(int &r, int &c)

{

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

     {

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

             {

                     if(sudoku[i][j]==0)

                     {

                                        r=i;

                                        c=j;

                                        return true;

                     }

             }

     }

     return false;

}

void displaysudoku()

{

     cout<<"\n\n";

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

     {

              cout<<"\n";

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

                      cout<<"  "<<sudoku[i][j];

     }

}

bool noconflict(int r,int c,int n)

{

   bool flag=true;

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

   {

           if(sudoku[i][c]==n && i!=r)

                              flag=false;

   }

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

   {

           if(sudoku[r][j]==n && j!=c)

                              flag=false;

   }

  

   int rstart=r-r%3,cstart=c-c%3;

   int rend=rstart+2,cend=cstart+2;

  

   for(int p=rstart;p<=rend;p++)

   {

           for(int q=cstart;q<=cend;q++)

           {

                   if(sudoku[p][q]==n && (p!=r && q!=c))

                                      flag=false;

           }

   }

   return flag;

}

            

bool solvesudoku()

{

     int row,col;

     if(!findunassignedcell(row,col))

     {

                                     displaysudoku();

                                     return true;

     }

     for(int num=1;num<=9;num++)

     {

             if(noconflict(row,col,num))

             {

                                      sudoku[row][col]=num;//assign

             }

             else

                 continue;

             if(solvesudoku())

                              return true;

            

              sudoku[row][col]=0;  //unassign

     }

     return false;

}

int main()

{

    cout<<"INTITIAL \n";

    displaysudoku();

    cout<<"\n\nSOLVED \n\n";

    solvesudoku();

    getch();

    return 0;

}

                                        

N QUEEN PROBLEM: On a NxN board place N queens such that no queen is under attack where a queen can move any steps horizontally, vertically and diagnolly.

public class Nqueen {

      private final int dim = 8;
      private final int queen = 1;
      private int[][] chessBoard  = new int[dim][dim];
      private int count = 0;
      private int startrow = 0;
   
      public void initialize()
      {
            setUpBoard();
            solve(0); 
            System.out.println("\n\nTOTAL NO. OF SOLUTIONS : " + count);
      }
   
 
   /*
         * This function checks whether a queen can be place in cell marked by (row,col)
         * If yes then returns true
         * Else returns false
   */
      public boolean isSafe(int row, int col)
      {
            for(int i=0; i<dim ; i++)
            {
                  if(chessBoard[i][col] == queen && i!= row)
                      return false;
                  if(chessBoard[row][i] == queen && i != col)
                      return false;
            }
         
            //diagnol check
            int i = row-1 , j= col-1;
            while(i>=0 && j>=0)
            {
                  if(chessBoard[i][j] == queen)
                      return false;
                  i--;
                  j--;
            }
         
            i = row+1;
            j=col+1;
            while(i<dim && j<dim)
            {
                  if(chessBoard[i][j] == queen)
                      return false;
                  i++;
                  j++;
            }
         
            i= row-1;
            j = col+1;
            while(i>=0 && j<dim)
            {
            if(chessBoard[i][j] == queen)
           return false;
            i--;
            j++;
            }
         
            i = row+1;
            j = col-1;
            while(i<dim && j>=0)
            {
                  if(chessBoard[i][j] == queen)
                       return false;
                  i++;
                  j--;
            }
            return true;
      }
   
 
   /*
         * This function initialized board to all 0's
   */
      public void setUpBoard()
      {
            for(int i=0; i<dim ; i++)
            {
                  for(int j=0; j<dim ; j++)
                  {
                      chessBoard[i][j] = 0;
                  }
            }
      }
   
 
   /*
         * This function place a queen at row, col position
   */
      public void placeQueen(int row, int col)
      {
            chessBoard[row][col] = queen;
      }
   
 
   /*
         * This function removes a queen placed at row, col position
   */
      public void removeQueen(int row, int col)
      {
            chessBoard[row][col] = 0;
      }
   
 
 
   /*
         * This function displays the chess board.
   */
      public void displayChessBoard()
      {
            for(int i=0 ; i< dim  ; i++)
            {
                  System.out.println();
                  for(int j=0 ; j<dim ; j++)
                  {
                      System.out.print(chessBoard[i][j] + "  ");
                  }
            }
      }
   
   
   /*
         * This function uses backtracking approach and check all possible test cases.
   */
      public void solve(int col)
      {
            if(col >= dim)
            {
                  count++;
                  System.out.println();
                  displayChessBoard();
                  return;
            }
            for(int row =startrow ; row<dim ; row++)
            {
                  if(isSafe(row,col))
                  {
                      placeQueen(row,col);
                      solve(col+1);
                      removeQueen(row,col);
                  }
            }
      }
   
 
      public static void main(String args[])
      {
            Nqueen n = new Nqueen();
            n.initialize();
      }
}

Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).

/*
Logic for this program is taken from a post on geeksforgeeks.
I couldn't deduce an O(n) logic.
*/

#include<conio.h>

#include<iostream.h>

void main()

{

      clrscr();

      int array[]={1,0,0,1,0,1,1};

      int len = sizeof(array)/sizeof(int);

      int *sum = new int[len];

      sum[0]=((array[0]==0)?-1:1);

      int min=array[0],max=array[0];

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

      {

            sum[i]=sum[i-1]+((array[i]==0)?-1:1);

            if(sum[i]>max)

                  max=sum[i];

            if(sum[i]<min)

                  min=sum[i];

      }

      int *hash = new [max-min+1];

      int maxsize =-1,startindex;

      for( i=0;i<max-min+1;i++)

            hash[i]=-1;

      for(i=0;i<len;i++)

      {

            if(sum[i]==0)

            {

                  maxsize=i+1;

                  startindex=0;

            }

            if(hash[sum[i]-min]==-1)

                  hash[sum[i]-min]=i;

            else

            {

                  if((i-hash[sum[i]-min]) > maxsize)

                  {

                        maxsize=i-hash[sum[i]-min];

                        startindex = hash[sum[i]-min];

                  }

            }

      }

      cout<<"\n START : "<<startindex;

      cout<<"\n END   : "<<maxsize+startindex-1;

      getch();

}

Without using extra space place all zeroes to left and 1's to right from an array of Zero's and 1's as below 011001 ans. 000111

#include<iostream.h>

#include<conio.h>

void main()

{

      clrscr();

      int a[]={0,1,1,0,0,1};

      int n=sizeof(a)/sizeof(int);

      int i=0,j=n-1;

      while(i<j)

      {

            if(a[i]==0)

                  i++;

            if(a[j]==1)

                  j--;

            if(a[i]==1 && a[j]==0)

            {

                  a[i]=0;

                  a[j]=1;

                  i++;

                  j--;

            }

      }

      for(i=0;i<n;i++)

            cout<<" "<<a[i];

      getch();

}

Find the subset of an array having maximum sum

#include<iostream.h>

#include<conio.h>

void main()

{

      clrscr();

      int a[]={1,3,-8,2,-1,10,-2,1};

      int n=sizeof(a)/sizeof(int);

      int sum=a[0];

      int max=-1;

      int start,end,s=0,e=0;

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

      {

            if(sum>=max)

            {

                  start=s;

                  end=e;

                  max=sum;

            }

            if(sum<0)

            {

                  s=e=i;

                  sum=a[i];

                  continue;

            }

            sum+=a[i];

            e=i;

      }

      cout<<max;

      getch();

}

There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: S = a[i] - a[j] where i>j and S > 0

#include<iostream.h>

#include<conio.h>

void main()

{

      clrscr();

      int arr[] ={-3,5,2,-2,1,0,-6,7,-8,2};

      int n=10,min=arr[0],max=-32767      ;

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

      {

            if(arr[i]<min)

            {

                  min=arr[i];

                  continue;

            }

            if(arr[i]-min>max)

                  max=arr[i]-min;

      }

      cout<<"MAX DIFFERENCE IS : "<<max;

            getch();

}

Find 3 numbers in the given array such that their sum is equal to a given number.

#include<iostream.h>

#include<conio.h>

int array[]={10,20,30,40,50,60,70,80,90};

int n=9;

int check(int k,int val)

{

      int i=0,j=n-1;

      static int flag;

      while(i<j)

      {

            if(i==k)

            {

                  i++;

                  continue;

            }

            if(j==k)

            {

                  j--;

                  continue;

            }

            if(array[i]+array[j]==val)

            {

                  cout<<"\n"<<array[i]<<" + "<<array[j]<<" + "<<array[k]<<" = "<<val+array[k];

                  flag++;

                  i++;

                  j--;

            }

            else if(array[i]+array[j]>val)

                  j--;

            else

                  i++;

      }

      return flag;

}

void main()

{

      clrscr();

      int val,flag;

      cout<<"Enter the value ";

      cin>>val;

      cout<<" \n\n";

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

            flag=check(i,val-array[i]);

      if(flag==0)

            cout<<"\n No such elements ";

      getch();

}

Inorder and Preorder tree traversal without recursion.

#include<iostream.h>

#include<process.h>

#include<math.h>

#include<conio.h>

class node

{

public:

      node *left;

      node *right;

      int data;

      node()

      {

            left=NULL;

            right=NULL;

      }

}*root=NULL;

int flag=0;

void add(node *parent,node *r,int d,int level,int item)

{

      if(r!=NULL)

      {

            add(r,r->left,d+1,level,item);

            add(r,r->right,d+1,level,item);

      }

      else if(d==level &&  flag!=1)

      {

            flag=1;

            node *newnode = new node;

            newnode->data=item;

            if(parent->left==NULL)

                  parent->left=newnode;

            else

                  parent->right=newnode;

      }

}

void npreorder()

{

      node *ptr=root;

      int top=-1;

      node **stack = new node*[50];

      while(1)

      {

            if(ptr!=NULL)

            {

                  cout<<"  "<<ptr->data;

                  if(ptr->right!=NULL)

                        stack[++top]=ptr->right;

                  ptr=ptr->left;

            }

            else

            {

                  ptr=stack[top--];

                  if(top==-2)

                        return;

            }

      }

}

void ninorder()

{

      node **stack= new node*[50];

      int top=0;

      node *ptr=root,*process=NULL;

      while(top>=0)

      {

            if(ptr && process!=ptr)

            {

                  stack[++top]=ptr;

                  ptr=ptr->left;

            }

            else

            {

                  ptr=stack[top--];

                  process=ptr;

                  cout<<"  "<<ptr->data;

                  if(ptr->right)

                        ptr=ptr->right;

            }

      }

}

void main()

{

      clrscr();

      int ch,item;

      cout<<"1.ADD\n2.PREORDER\n3.DEPTH\n4.NO OF ELEMENTS\n5.TRACE";

      cout<<"\n6.BFS AND DFS\n7.EXIt";

      while(1)

      {

            cout<<"\nchoice? ";

            cin>>ch;

            switch(ch)

            {

                  case 1: cout<<"ITEM :";

                        cin>>item;

                        flag=0;

                        if(root==NULL)

                        {

                              node *newnode = new node;

                              newnode->data=item;

                              root=newnode;

                        }

                        else

                        {

                              maxdepth=0;

                              depth(root,0);

                              int level;

                              int elements=count(root);

                              if(elements==(pow(2,maxdepth+1)-1))

                                    level=maxdepth+1;

                              else

                                    level=maxdepth;

                              add(root,root,0,level,item);

                        }

                        break;

                  case 2: ninorder();

                        //npreorder();

                        //preorder(root);

                        break;

                  case 3: maxdepth=0;

                        depth(root,0);

                        cout<<maxdepth;

                        break;

                  case 4: cout<<count(root);

                        break;

                  case 5: equal=0;

                        cout<<"ITEM TO TRACE : ";

                        cin>>item;

                        trace(root,item);

                        break;

                  case 6: cout<<"\nBFS\n";

                        bfs();

                        cout<<"\nDFS\n";

                        dfs();

                        break;

                  case 7:     exit(0);

            }

      }

}

Count the number of elements in a binary tree.

int count(node *r)

{

      if(r==NULL)

            return 0;

      else

      {

            int c=1;

            c+=count(r->left);

            c+=count(r->right);

            return c;

      }

}

calculate the depth of the binary tree.

int maxdepth=0;

void depth(node *r,int d)

{

      if(r!=NULL)

      {

            if(maxdepth<d)

                  maxdepth=d;

            depth(r->left,d+1);

            depth(r->right,d+1);

      }

}