CareerCup

Overkill O(n^2) solution.

Preprocess for Range Minimum and Maximum queries. (O(n)) time.

For each sub-array, figure out in O(1) time whether max-min = length - 1. O(n^2) time.

public static void question1(int []input)
	{
		int[] longest=new int[input.length];
		longest[0]=1;
		for(int i=1;i<input.length;i++)
		{
			int longest_=1,min=input[i],max=input[i];
			Set<Integer> set=new HashSet<Integer>();
			set.add(input[i]);
			for(int j=i-1;j>=0;j--)
			{
				if(set.contains(input[j]))
				{
					break;
				}
				else
				{
					set.add(input[j]);
				}
				max=Math.max(max, input[j]);
				min=Math.min(min,input[j]);
				if(i-j==max-min)
				{
					longest_=Math.max(longest_,i-j+1);
				}
			}
			longest[i]=longest_;
		}
		int longestValue=1,longestIndex=0;
		for(int i=1;i<longest.length;i++)
		{
			if(longest[i]>longestValue)
			{
				longestValue=longest[i];
				longestIndex=i;
			}
		}
		int startIndex=longestIndex-longestValue+1;
		for(int i=startIndex;i<=longestIndex;i++)
		{
			System.out.print(input[i]+",");
		}
		System.out.println("");
		System.out.println("longestValue: "+longestValue+" longestIndex: "+longestIndex);
	}

The approach I took was to start from the first element in the array. I would look from the other end of the array to find the next adjacent element if one exists. I defined adjacent as n, n-1, or n+1. If I found an adjacent element, I made a subarray of elements between my starting an ending points and checked to see if the elements inside were all consecutive. (To test this I used a built-in sort and walked up the subarray to see if there were any gaps.) If it was valid, I compared it against my previous best, and stored the answer if necessary. If the subarray was invalid, I searched for the next adjacent element for my current index and repeated the process.

This took me about an hour to get a working solution and for the record I think this would make a terrible interview question. :) As a coding puzzle it was kinda fun I guess...

There are some optimizations I could make, for example, I could stop searching if array.length - current index < bestEnd - bestStart. My algorithm complexity is something like O(n^2) + time for the inner-array sorting.

static int[] findLongest(int[] array)
        {
            int bestStart = 0, bestEnd = 0;

            // Example {4, 5, 1, 5, 7, 6, 8, 4, 1}
            // Result {5, 7, 6, 8, 4}

            // from the start, find border numbers
            for (int i = 0; i < array.Length; i++)
            {
                bool validRange = false;

                int furthestAdjacent = indexOfAdjacent(array, i, array.Length - 1);
                while (furthestAdjacent != -1 && !validRange)
                {
                    // Check to see if this range is worth investigating
                    if (furthestAdjacent - i > bestEnd - bestStart)
                    {
                        List<int> subarray = CopyAndSort(array, i, furthestAdjacent);
                        validRange = ValidateSub(subarray);
                    }
                    else
                    {
                        break;
                    }

                    if (!validRange)
                    {
                        furthestAdjacent = indexOfAdjacent(array, i, furthestAdjacent - 1);
                    }
                }

                // If we found a valid range, store it
                if (validRange)
                {
                    if ((furthestAdjacent - i) > (bestEnd - bestStart))
                    {
                        bestStart = i;
                        bestEnd = furthestAdjacent;
                    }
                }
            }

            int[] result = new int[bestEnd - bestStart + 1];
            int index = 0;
            for (int i = bestStart; i <= bestEnd; i++)
            {
                result[index] = array[i];
                index++;
            }

            return result;
        }

        private static bool ValidateSub(List<int> subarray)
        {
            if (subarray.Count <= 0)
            {
                return false;
            }

            int last = subarray[0];
            for (int i = 1; i < subarray.Count; i++)
            {
                if (subarray[i] == last || subarray[i] == last + 1)
                {
                    last = subarray[i];
                }
                else
                {
                    return false;
                }
            }

            return true;
        }

        private static List<int> CopyAndSort(int[] array, int i, int furthestAdjacent)
        {
            List<int> list = new List<int>();
            for (; i <= furthestAdjacent; i++)
            {
                list.Add(array[i]);
            }

            list.Sort();
            return list;
        }

        static int indexOfAdjacent(int[] array, int lowest, int highest)
        {
            // TODO validate params

            for (int i = highest; i > lowest; i--)
            {
                // lowest is the element we're comparing against
                if (array[i] <= array[lowest] + 1 && array[i] >= array[lowest] - 1)
                {
                    return i;
                }
            }

            return -1;
        }

void getLongestContSeq(int a[], int n){
     int lStart = 0, lEnd = 0;
     int start = 0, end = n-1;
     
     // Sort the array
     sort(a, a+n);
     
     // remove the duplicates
     int *r = new int[n];
     int cnt = 0;
     r[cnt++] = a[0];
     
     for (int i=1;i<n;i++){
         if ( a[i] - a[i-1] != 0 ) r[cnt++] = a[i];
     }
     // Find the subsequence
     for (int i=0;i<cnt;i++){
         if ( (r[i+1] - r[i] != 1) || (i == cnt-1)) {
              end = i;
              if ( (end - start) > (lEnd - lStart) ){
                  lStart = start;
                  lEnd = end;
              }
              start = i+1;
         }
     }
     lEnd = lEnd+1;
     
     for ( int i=lStart;i<lEnd;i++ )
         cout << r[i]<<", ";
}

Take two pointers A at start and B at the end.
a. Transverse through the array and find out the min max ,sum of array and number of elements.
b. check the possibility of the array is consecutive i.e sum of integers upto MAX element - sum of integers up to MIN-1 is equal to sum of array using N(N+1)/2. If yes check Digits are non repeating. If yes store the indexes and count of sub array and do A++. Else do B--. Sum = Sum-B. if B is not MIN or MAX nothing to do else look for MIN and MAX between A and B.

repeat the step B until it reached A + Max array length found..

Do A++, B=length of array

1. Match the value with index. Create another array (let's say, Boolean indexArr) that has size of the max value of the given array. Using the given example, the size should be 8 + 1. Run through the given array (let's say, valArr), mark TRUE the indexArr[valArr[i]]. At the end you will get a array looking like this {F, T, F, F, T, T, T, T, T}.
2. Create an empty vector (let's say, resultVec).
3. Loop through valArr, if (indexArr[valArr[j]] == true) then result.add(valArr[j]), else (meaning it's not consecutive) result.clear() to start over again.

How about this (code in Python):

def longest_subarray(array):
    # Make the array a *set* to remove duplicate and to make ``in`` operator 0(1).
    array = set(array)
    longest = []
    # Loop over all element of array in 0(n).
    for val in array:
        # Get all consecutive value of ``val`` that are in ``array``.
        tmp = []
        while val in array:
            tmp.append(val)
            val += 1
        # Check if the new list is the biggest.
        if len(tmp) > len(longest):
            longest = tmp
    return longest

Here is an idea of O(n*logm) amortized time. n = "length of the array" and m = "length of longest continuous sequence".
Here is the array A[]= {4,5,1,5,7,6,8,4,1} (from the example)

The idea is to use a HashMap<Integer, TreeNode> hMap (TreeNodes will be sorted by the index in the array). Here are steps:
1.) start traversing A[i], i = 1..n, and add it in the hMap as follow:
1.1.) if hMap.contains(A[i])
1.1.1) traverse the tree in A[i] and check if this is currently longest result. (here we do versioning of the Tree so if we have already checked the tree previously do not do it again.)
1.1.2) cut the left subtree at A[i]
1.2) else
1.2.1) If hMap.contains(i-1/i+1) merge the Trees A[i - 1] + A[i] + A[i + 1]
1.2.2) else just add the value to hMap
2.) Finally iterate the hMap and do 1.1.1) point

this can be done by o(n) complexity...

#include<stdio.h>
void main()
{

int a[]={1,2,-5,6,-5};
int i,j,k,l;
int max=0,count;

for(i=0;i<5;i++)
{
count=a[i];
for(j=i+1;j<5;j++)
{
count+=a[j];
if(count>max)
{
max=count;
k=i;
l=j;
}
}
}

for(i=0;i<5;i++)
if(max<a[i])
{
max=a[i];
k=i;
l=0;
}

if(l)
printf(" group size =%d max value=%d strating=%d end=%d",l-k+1,max,k,l);
else
printf(" group size =1 max value=%d starting=%d",max,k+1);
}

int[] input; //original input
int[] sortedInput; //contains input array sorted in non-decreasing order
int[] originalIndices //originalIndices[i] contains the original index in the input for any element sortedInput[i] (0 < i < input.length)
int[] startsAt; //inititialized to startsAt[i] = i (0 < i < input.length)
int[] endsAt; //initialized to endsAt[i] = i (0 < i < input.length)
int[] startsAtLastValue; //initialized to startsAtLastValue[i] = input[i] (0 < i < input.length)
int[] endsAtLastValue; //initialized to endsAtLastValue = input[i] (0 < i < input.length)


for(int i = 0; i < input.length; i++) {
	int originalIndex = originalIndices[i];
	int value = sortedInput[i];
	
	if(originalIndex > 0 && (value - endsAtLastValue[originalIndex - 1]) == 1) {
		endsAtLastValue[originalIndex] = value;
		endsAt[originalIndex] = endsAt[originalIndex - 1];
		startsAt[endsAt[originalIndex]] = originalIndex;
		startsAtLastValue[endsAt[originalIndex]] = value;
	}

	if(originalIndex < (input.length - 1) && (startsAtLastValue[originalIndex + 1] - value) == 1) {
		startsAtLastValue[originalIndex] = value;
		startsAt[originalindex] = startsAt[originalIndex + 1];
		endsAt[startsAt[originalindex]] = originalIndex;
		endsAtLastValue[startsAt[originalindex]] = value;
	}
}


//Find i such that startsAt[i] - i is maximum. For this i, input[i...startsAt[i]] will have output.

//Here is the dp solution

#include<iostream.h>
#include<conio.h>
# define disp(a,n,s)  for (int i=s;i<n;i++) cout<<a[i]<<" "; 
using namespace std;

int mem[100]={0};

void max(int a[],int n,int *start,int *end)
{
    int max=a[0];
    *start=0;
    *end=0;
    for (int i=1;i<n;i++)
    {
        if(max<=a[i])
        {
              max=a[i];
              *end=i;      
        }
        
    }
    for(int i=*end;i>=0;i--)
    {
            if(a[i]==1)
            {*start=1;break;}
    }
}
    

void dp(int a[],int n,int i)
{
     if(i==n-1)
     return;
     if(a[i-1]<=a[i])
     mem[i]=mem[i-1]+1;
     else
     mem[i]=1;
     
     dp(a,n,i+1);
     
}

int main()
{
    int a[]={4,5,1,5,7,6,8,4,1},x=0,y=0;
    dp(a,sizeof(a)/sizeof(int),0);
    int n;
    n=sizeof(a)/sizeof(int);
    /*disp(a,n,0);
    cout<<endl;
    disp(mem,n,0);*/
    max(mem,n,&x,&y);
    cout<<endl;
    disp(a,y+1,x);
    getch();
    return 0;
}

#include<stdio.h>
void maxsize(char *s);
void fill(char *,int*,int,int);
int sequence(int*,int);
main()
{
char s[100];
printf("enter string\n");
scanf("%s",&s);
maxsize(s);
}


void fill(char *s,int *table,int j,int k)
{
int i;
for(i=j;i<=k;i++)
table[s[i]-97]++;
}

void maxsize(char *s)
{
int gap,k,j,max,start;
int n;
int table[26];
n=strlen(s);
for(gap=1;gap<n;gap++)
{
for(j=0,k=gap;k<n;k++,j++)
{
memset(table,0,26);
fill(s,table,j,k);
if(sequence(table,gap+1))
{
max=gap;
start=j;
}
}
}

for(j=start;j<=start+max;j++)
printf("%c",s[j]);
}

int sequence(int *table,int size)
{
int i;
int count=0,found=0;
for(i=0;i<26;i++)
{
if(!found && table[i])
{
found=1;
count=1;
}
else if(found && !table[i])
break;
else if(table[i])
count++;
}

return count==size;
}

Pseudo code (Sliding subarray of decreasing size):
1. Start with a subarray whose size = arrays length.
2. Check if this subarray is a valid contiguous subarray (algo to check follows)
3. If yes, print it.
4. If no, reduce the subarray size by 1 and start with index 0 of main array, slide the subarray until last element of main array is part of the subarray
5. Repeat step 2-4 until subarray.length > 1
6. No subarray exists if nothing found so far.


Pseudo-code for checking any given subarray is valid or not:
1. For a subarray, set starting index as 0 do the following
2. If subarray[index] > subarray.length, fail test - Number at index pos is too large to fit in this subarray; return
3. Else Check value at subarray[subarray[index]-1]. If value is same as subarray[index]-1, there is a repeating number in this subarray so fail test - return.
4. Else capture subarray[subarray[index]-1] as newIndex; set subarray[subarray[index]] = subarray[index]-1. Set index = newIndex
5. Repeat from 2.

void longestSubarray(int a[])
{
    int n=sizeof(a)/sizeof(a[0]);   //length of array
    int max=0,*hash;
    int subArray_start=0,subArray_end=0;
    for(int i=0;i<n;i++)         //get maximum and minimum in array
    {
        if(max<a[i])
          max=a[i];  
    }
    hash=new int[max+1]();  //array values initialized to zero
        
    for(i=0;i<n;i++)
    {
       if(hash[a[i]]==1)
        { 
           delete hash;
           hash=new int[max-min+1]();
           subArray_start=i--;    //initialize start of subarray
           continue;  
        }
       hash[a[i]]=1;
    }
    
    int tmp_strt=0,tmp_end=0;
    for(i=0;i<=max;i++)    
    {
       if(hash[i]==1 && (hash[i-1]==0|| i>=0))
         tmp_start=i;
       if(hash[i]==0)
         tmp_end=i-1;
    }
    if(!tmp_end)
     tmp_end=i-1;
    
    while(n)
    {
       if(a[n]<=tmp_end || a[n]>=tmp_strt)
         subArray_end=n;      //initialize end of subarray
       n--;
    }

    for(i=subArray_start;i<=subArray_end;i++)   //print output
     cout<<a[i]<<" ";

}

Time Complexity - O(4n)
This code will give a problem with negative numbers...Any ideas of improvement??

when u find a repeating elemnt check if min+max-1 is equal to number of elemnts encounterd!!
if so then it was a consecutive sequence..

thn clear thee hash table used to check the repetition..check for forward..

This is my solution,
1)find the max value, create and array of that size and make each value present to one.
2) now find the sequence of 1's and find the rage of the indexes.
3) print the output.
Here is the below code.

#include<stdio.h>
#include<malloc.h>

int main()
{
	int array[9] = {4,5,1,5,7,6,8,4,1},i,max = array[0],maxindex,minindex,count = 0,maxcount = 0;
	/*finding the max*/
	for(i = 0; i<9;i++) {
		if(array[i] > max)
			max = array[i]; 
	}
	int  *array1 = (int *)calloc(max,sizeof(int));
	for(i = 0; i<9 ; i++) 
		array1[array[i]] = 1;
	for(i=0; i<9; i++) {/*find the range index*/
		count = 1;
		if(array1[i] == 1) {
			while(array1[i] == array1[i+1]) {
         			count++;
				i++;
			}
			if(count > maxcount) {
				maxcount = count ;
				minindex = i - count;
				maxindex = i - 1;
			}
		}
	}
	for(i=minindex; i<=maxindex; i++) /* print the outpupt*/
		printf("output : array[%d] = %d\n",i,array[i]);
	printf("count = %d\n",count);
	printf("maxindex = %d minindex = %d\n",maxindex,minindex);
	free(array1);
	return 0;
}

int findLength(int arr[], int n)
{
    int max_len = 1;  // Initialize result
    for (int i=0; i<n-1; i++)
    {
        // Initialize min and max for all subarrays starting with i
        int mn = arr[i], mx = arr[i];
 
        // Consider all subarrays starting with i and ending with j
        for (int j=i+1; j<n; j++)
        {
            // Update min and max in this subarray if needed
            mn = min(mn, arr[j]);
            mx = max(mx, arr[j]);
 
            // If current subarray has all contiguous elements
            if ((mx - mn) == j-i)
                max_len = max(max_len, mx-mn+1);
        }
    }
    return max_len;
}

This comment has been deleted.

1. sort the array in extra space..
2. find the max length of consecutive range, min and max of that range.. here length = 5, max = 8, min= 4
3. create an array[length (or) max-min+1]... here array[5]..
4. now traverse the original input with count = 0
a) if the element is within the calculated range, increase the count and array[element-min] set to 1
b) if the element is repeated(which is already set in the array[]) or out of range.. check whether the element in array[] are consecutively set to 1.. if it is, store that temporary output with count.. reset count and array[] to zero
c) repeat a).. if the count exceeds the previous count.. update it..

Note: we have to iterate through all range of values..
for example: {1,2,3,51,7,52,8,53,9,54,10,55}
i)first process with 51..55
ii)next with 7...10
iii)next with 1..3
if i) is found to be continous in input with length = 5 then no need to see for ii) and iii) as they have length less than 5..

@leet,
"For ex- {4,5,1,5,7,6,8,4,1}
output-{5,7,6,8,4}.Find the longest."
continuous sequence means subarray in some sorted fashion ?? if yes, then how 5,7,6,8,4 is the ans of above example, ?? can you please explain your question

Mark for consideration.