Q. Given a list of integers find out the biggest interval that has all the numbers in the given list

INPUT  1,8,4,6,3,2,7,11;

Possible  candidates  will  be  1,2,3,4  and  6,7,8  as  they  are  the  continous  elements  present  in  the  input  array

But  1,2,3,4  is  having  more  length  so  it  will  be  the  answer

OUTPUT  [1,4];

METHOD  1

Sort  all  elements  and  check for  the  biggest  interval  in  the  sorted  array

1.  After  using  merge  sort  ,  

     int length=1;//  length  will  be  our  answer

     int maxYet=1;

     for(int i=1 to n)

     {

      if(a[i]==a[i-1])

      {

       maxYet++;

     }

       else

       //resetset  maxYet  and  compare

        {

          if(maxYet>length)

           length=maxYet;

      

          maxYet=1;

        } 

      

     }

Time Complexity=O(n logn)
Space Complexity=O(1)

METHOD  2

It  really  took  time  to  think  that  one   

It  involves  hash...

1.  Scan  all the  elements  and  hash  in  2  hashmaps  (visited  and  present) all  elements.

2.  int  length=1,maxYet=1;

    visited[element]=0;

   present[element]=1;
3.  For  every  element  if  not  visited   , check  if  consecutive  predecessors  are  present  in  array  and  mark  them  as  visited

4.  Similarly  do  for  consecutive  successor  elements

5. Now  higher-lower  will  be  our  length,  if  that  is  maximum  than  previous  one  then  it  is  taken  as  result.

#include<iostream>
#include<map>
#include<string>

using namespace std;
typedef map<int,int> mapping;

int main() 
{
mapping visited;
mapping present;

int length=1,res1=-1,res2=-1;
int arr[10]={1,7,4,6,3,10,2,9,13,11};

for(int k=0;k<10;k++)
{
visited[arr[k]]=0;
present[arr[k]]=1;
}


for(int k=0;k<10;k++)
{
int element=arr[k];int lower=arr[k],higher=arr[k];

if(visited[element]==0)
{
while(present[element]==1)
{
lower=element;
visited[element]=1;
element--;
}

element=arr[k]+1;
while(present[element]==1)
{
higher=element;
visited[element]=1;
element++;
}

if((higher-lower)>length)
{
res1=lower;res2=higher;length=higher-lower;
}
}
}
if(res1==-1 && res2==-1)
printf("No consecutive element");
else
printf("%d %d",res1,res2);
return 0;

}

Time  Complexity=O(n)
Space Complexity=O(n)

-