CareerCup

int length = sortedArray.length;
int length_longest_sequence = 0;
int temp_length_longest_sequence = 0;

int min = 0;

for(int idx = 1; idx < length; idx++) {
	if(sortedArray[min] == sortedArray[idx]) {
		continue;
	}
	
	if (sortedArray[min] +1 = sortedArray[idx]) {
		temp_length_of_longest_sequence++;
	} else if (sortedArray[min] + 1 < sortedArray[idx]) {
		if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_longest_sequence = temp_length_longest_sequence;
		}
		min = idx;
		temp_length_longest_sequence = 0;
	}
}

if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_sequence = temp_length_longest_sequence;
        }

Use MergeSort to sort the array and also keep track of the indices of the elements in another index[] array.

Traverse through the array and find the max range.

It can be done in linear time using a hashtable:

size_t winner = 0;
auto map = new std::hash_map<int, int>();
for (size_t i = 0; i < num_items; ++i) {
  auto it = map.find(items[i] - 1);
  if (it != map.end()) {
    winner = max(i - *it);
  }
  map[items[i]] = i;
}

printf("winner: %du\n", winner);

Can also be done using counting sort in O(n).

Sort the array - O(nlogn)

On the sorted array, sortedArray[]

int length = sortedArray.length;
int length_of_longest_sequence = 0;
int temp_length_of_longest_sequence = 0;

int min = 0;

for(int idx = 1; idx < length; idx++) {
	if(sortedArray[min] == sortedArray[idx]) {
		continue;
	}
	
	if (sortedArray[min] +1 = sortedArray[idx]) {
		temp_length_of_longest_sequence++;
	} else if (sortedArray[min] + 1 < sortedArray[idx]) {
		if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_longest_sequence = temp_length_longest_sequence;
		}
		min = idx;
	}

	if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_longest_sequence = temp_length_longest_sequence;
        }
}

screwed up while using variables. this should be it

The logic is that such sequence will have a sequence of same number being minimum and sequence of some other number being the maximum

int length = sortedArray.length;
int length_longest_sequence = 0;
int temp_length_longest_sequence = 0;

int min = 0;

for(int idx = 1; idx < length; idx++) {
	if(sortedArray[min] == sortedArray[idx]) {
		continue;
	}
	
	if (sortedArray[min] +1 = sortedArray[idx]) {
		temp_length_of_longest_sequence++;
	} else if (sortedArray[min] + 1 < sortedArray[idx]) {
		if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_longest_sequence = temp_length_longest_sequence;
		}
		min = idx;
	}

	if(temp_length_longest_sequence > length_longest_sequence) {
			length_longest_sequence = temp_length_longest_sequence;
        }
}

shucks !. the last if block should be out of the for loop :(

O(n^2)

package com.amazon.practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Sequence implements Comparable<Sequence>{
	private int length=0;
	public List<Integer> seq = new ArrayList<Integer>();
	private int minElement=Integer.MAX_VALUE;
	
	public Sequence(){
		
	}
	public Sequence(int i){
		this.add(i);
	}
	public void add(int i){
		this.seq.add(i);
		this.length++;
		if(i<this.minElement)
			this.minElement = i;
	}
	
	public int getMinElement(){
		return this.minElement;
	}
	
	@Override
	public int compareTo(Sequence arg0) {
		// TODO Auto-generated method stub
		if(this.length > arg0.length)
			return -1;
		if(this.length < arg0.length)
			return 1;
		return 0;
	}
	
	@Override
	public String toString(){
		return seq.toString();
	}
}

public class SeqProblem {
	public static void main(String[] arg){
		int[] array = {6,10,6,7,8,6,7};
		Queue<Sequence> pq = new PriorityQueue<Sequence>();
		
		for(int i=0;i<array.length;i++){
			Iterator<Sequence> it = pq.iterator();
			pq = updateQueue(it,array[i],pq);
		}
		
		System.out.println(pq.poll());
	}
	
	public static Queue<Sequence> updateQueue(Iterator<Sequence> it,int i,Queue<Sequence> pq){
		//copy the original queue into temp
		Iterator<Sequence> it1 = pq.iterator();
		Queue<Sequence> pqTmp = new PriorityQueue<Sequence>();
		while(it1.hasNext()){
			pqTmp.add(it1.next());
		}
		
		while(it.hasNext()){
			Sequence s = it.next();
			if(Math.abs(s.getMinElement()-i)<=1){
				pqTmp.remove(s);
				s.add(i);
				pqTmp.add(s);
			}				
		}
		pqTmp.add(new Sequence(i));
		//return updated queue
		return pqTmp;
	}
}

seq {6,6,7} diff is 1 len 3

Clarification- why do we consider 6,6,7 when there is no such continuous sub-array in the array listed ? So it need not be a continuous sequence ?

Should the 3 elements be in the same order at least? If not, then sorting and counting the occurrences seems to be the best idea.

Create a BST. Traverse the tree. If difference between parent and child is 1, increment the count. Also, keep the count of number of times the element is appeared so that the count can be incremented appropriately.

should the sequence be increasing or just a subsequence

should the sequence be increasing or just a subsequence

"In this example the program should return 3 ."

Shouldn't it return 5?

For e.g. array[]={6,10,6,7,8,9,0} 
seq {10,6,7,8,9} diff is 1 len 5

int GetLongestSequence(int[] arr, int max, int min)
{
   int countArrLen = max-min+1;
   if(countArrLen<2) return -1;

   int[] counts = new int[countArrLen];
   for(int i=0;i<counts.length;++i)
   {
      counts[i]=0;
   }

   for(int i=0;i<arr.length;++i)
   {
      counts[arr[i]-min]++;   
   }

   int maxLen = INT_MIN;
   for(int i=0;i<counts.length-1;++i)
   {
      if(counts[i]==0 || counts[i+1]==0) continue;
      int seqLen = counts[i]+counts[i+1];
      if(seqLen>maxLen)
      {
         maxLen=seqLen;
      }
   }

   return maxLen;
}

O(n) time complexity.

// time: O(N*lgN)
// space: O(1)

int run(int[] arr, int index){
		
		int pivot = arr[index];
		
		for( int i = index+1; i < arr.length; i++ ){
			if( arr[i] != pivot ){
				return i-1;
			}
		}		
		
		return arr.length-1;
	}
	
	void printLongestSequence(int[] arr){
		Arrays.sort(arr);
	
		int maxLength = 0;
		int maxStart = -1;
		int maxRight = -1;
		
		int start = 0;
		
		while( start < arr.length ){
			
			int left = run(arr, start);
			
			if( left == arr.length-1 ){
				break;
			}
			
			int right = run(arr, left+1);
			
			if( Math.abs(arr[left]-arr[right]) == 1 ){
				int curLength = (left-start+1) + (right - (left+1)+1);
				
				if( curLength > maxLength ){
					maxLength = curLength;
					
					maxStart = start;
					maxRight = right;					
				}
			}
			
			start = left+1;
		}
		
		List<Integer> seq = new ArrayList<>();
		for( int i = maxStart; i <= maxRight; i++ ){
			seq.add( arr[i] );
		}
		
		System.out.println( seq );
		
	}

private static int getlongest(int[] arr)
{
if (arr.Length == 0)
return 0;

Array.Sort(arr);

int left = 0;
int secondLeft = 0;
int right = 1;
int longest = 1;
int finalLongest = 1;
int dif = 0;

while(right < arr.Length)
{
dif = arr[right] - arr[left];
if (dif <= 1)
{
if (dif == 1 && secondLeft == left)
{
secondLeft = right;
}
right++;
longest = right - left;
}
else
{
if (left != secondLeft)
left = secondLeft;
else
left = right;

if (dif > 2)
secondLeft = left;

if (longest > finalLongest)
{
finalLongest = longest;
}
longest = right - left;
right++;
}
}

return finalLongest;
}

private static int getlongest(int[] arr)
        {
            if (arr.Length == 0)
                return 0;

            Array.Sort(arr);

            int left = 0;
            int secondLeft = 0;
            int right = 1;
            int longest = 1;
            int finalLongest = 1;
            int dif = 0;

            while(right < arr.Length)
            {
                dif = arr[right] - arr[left];
                if (dif <= 1)
                {
                    if (dif == 1 && secondLeft == left)
                    {
                        secondLeft = right;
                    }
                    right++;
                    longest = right - left;
                }
                else 
                {
                    if (left != secondLeft)
                        left = secondLeft;
                    else
                        left = right;

                    if (dif > 2)
                        secondLeft = left;

                    if (longest > finalLongest)
                    {
                        finalLongest = longest;
                    }
                    longest = right - left;
                    right++;
                }
            }

            return finalLongest;

}

C++ approach. o(n) time complexity solution.

{

int determineLength(int * arr, int length)
{
	int max_extension = 0;
	map<int, int, cmp> m;
	
	for(int i = 0; i < length; i++)
		m[arr[i]]++;
	
	map<int, int>::iterator stop = m.end();
	stop--;
	
	int key, value;
	
	for(map<int, int>::iterator it = m.begin(); it != stop; it++)
	{
		key = it->first;
		value = it->second;
		it++;
		if(it->first - key <= 1)
			if(it->second + value > max_extension)
				max_extension = it->second + value;
		it--;
	}
	return max_extension;
}

}

public static int largestSequence(ArrayList<Integer> a)
{
	Collections.sort(a);
	int min = a.get(0);
	int max=a.get(1);
	int startIndex=0;
	int stopIndex=1;
	for (int i=1; i<a.size()-1; i++){

		max = a.get(i+1);
		if (Math.abs(min-max) >1)
		{
			min = a.get(i);
			startIndex += 1;
			stopIndex += 1;
		}
		else{
			max = a.get(i+1);
			stopIndex +=1;
		}		
	}
	return stopIndex-startIndex+1;
}

Solution complexity is O(n)

{{

package hashtable;

import java.lang.*;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;


public class HashTableDemo {

public static void main(String[] args) {
Hashtable<Integer,Integer> ht = new Hashtable<Integer,Integer>();
int arr[] = {6,10,6,21,2,33,12,7,7,8,9,0};
int max_len = 0;
for(int i =0; i < arr.length; ++i)
{
if(!ht.containsKey(arr[i]))
{
ht.put(arr[i], i);

}
if(ht.containsKey(arr[i] - 1))
{
int start_index = ht.get(arr[i] - 1);
if(Math.abs(start_index - i) > max_len)
max_len = Math.abs(start_index - i);
System.out.println("Start : " + start_index + "End :" + i);
System.out.println("Max length : " + max_len);
continue;
}
if(ht.containsKey(arr[i] + 1))
{
int start_index = ht.get(arr[i] + 1);
if(Math.abs(start_index - i) > max_len)
max_len = Math.abs(start_index - i);
System.out.println("Start : " + start_index + "End :" + i);
System.out.println("Max length : " + max_len);
continue;
}
else
{

}


}
System.out.println("Max length : " + max_len);

}


}

}}

Unless I got the question wrong, in your example, {10, 6, 7, 8, 9} should be the solution. The length is 5 and the diff of max and min is 4.

The way I understand from examples is that you are looking for a subset of numbers (rather than sequence since you mentioned it is not sequential) such that their max - min is 1 + size of the subset.

The algorithm I found for it is the following:
1) Sort the numbers (ascending)
2) Subtract "i" from number at index "i".
3) After subtraction, look for indices with the same value. The longest difference in indices is your length.
In your example:
1) sort => {0 6 6 7 8 9 10}
2) remove "i": {0 5 4 4 4 4 4}
3) similar keys (5 x "4") => {6, 7, 8, 9, 10}

For integers, this runs in linear time (count/radix sort). In general NxLog(N) for comparison-based sorting.

{
Sequence where Difference between largest and smallest element is 1 is same as Sequence where all middle elements are either equal to smallest or equal to largest.
-
Solution:
cur_low, cur_high, cur_count init to -1

Use hash to store -> index of element in arr[], count.
While inserting x, look for y such that y - x = 1 && y.index > x.index && x.count + y.count > cur_count
-> cur_count = x.count.y.count
-> cur_low = x.index
-> cur_high = y.index
}

Logic:
1.sort the array using Arrays.sort in java which takes nlog(n) time.
2.then use 3 pointers called start,new element and end.(I mean indexes when I say pointers as I am coding in Java.)
3.end starts from 2nd element and so does newElement.
4.compare end and end-1
1.if the difference is 0 then just increment end.
2.if the difference is 1:
case1:if end+1 - end == 0 then increment end
case2:else start points to newElement and new Element to End.
(Basically new Element keeps track of first non repeating number in the sequence i.e if ur sequence is :1,1,1,2,2,2,3....newElement points to 2.)

The complete code is given below. Do let me know if it fails:

import java.util.ArrayList;
import java.util.Arrays;

public class LongestSequenceDifference {

	public static int getLongestSequenceDifference(int [] input){
		Arrays.sort(input);
		int start = 0,end = 1, newElement=1,maxLength = 0,currentMax = 1;
		for(int index = 0 ; index < input.length; index++){
			if(end < input.length && (input[end] - input[(end-1)] == 0)){
				end += 1;
				currentMax += 1;
			}
			else if(end < input.length && (input[end] - input[(end-1)] == 1)){
				
				if((end+1 < input.length && input[end+1] - input[(end)] == 0) && input[end+1]-input[start]==1){
					newElement = end;
					currentMax += 1;
				}
				else{
					currentMax = 1;
					start = index = newElement;
					newElement = end;
				}
				end += 1;
				
			}
			else{
				end += 1;
			}
				if (currentMax > maxLength)
					maxLength = currentMax;

			}	
			return maxLength;
		}

		public static void main(String[] args) {
			// TODO Auto-generated method stub
			int[] input = { 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 8, 9, 10 };
			//int[] input = {1,2,3,4,5};
			System.out.println(getLongestSequenceDifference(input));
		}

	}

My Solution in Java using TreeMap. please check if it fails for anyone

static void findSequence(){
		int [] arr =  {6,10,6,7,8,9,0,10,10,1,1,1,2,1} ;
		TreeMap<Integer,Integer> tM = new TreeMap<Integer, Integer>();
		for(int i=0; i<arr.length; i++){
			if(tM.containsKey(arr[i])){
				tM.put(arr[i], tM.get(arr[i])+1);
			}else{
				tM.put(arr[i],1);
			}
		}

		Set s = tM.entrySet();
		Iterator itr = tM.entrySet().iterator();
		int maxLen = 0;
		int key = 0;
		int prevKey =0;
		int keyVal = 0;
		int prevKeyVal =0;
		int i =0;
		
		Map.Entry<Integer, Integer> mPrev = null;
		while(itr.hasNext()){
			
			Map.Entry<Integer, Integer> mNext = (Map.Entry<Integer, Integer>)itr.next();
			if(mPrev!=null){
				int tmpCurrKey = mNext.getKey();
				int tmpPrevKey = mPrev.getKey();
				int tmpCurrVal= mNext.getValue();
				int tmpPrevVal = mPrev.getValue();
				
				if((tmpCurrKey - tmpPrevKey)  == 1){
					if(maxLen < (tmpCurrVal + tmpPrevVal)){
						maxLen = tmpCurrVal + tmpPrevVal;
						prevKey = tmpPrevKey;
						key = tmpCurrKey;
						prevKeyVal = tmpPrevVal;
						keyVal = tmpCurrVal;
					}
				}
			}
			mPrev = mNext;
		}
		
		for(int j =0; j<prevKeyVal;j++){
			System.out.print(prevKey+" ");
		}
		for(int j =0; j<keyVal;j++){
			System.out.print(key+" ");
		}
		System.out.println("");
		System.out.println("Max Len "+maxLen);
	}

int getMaxLengthDiffOne(vector<int> input)
{
    sort(input.begin() , input.end());
    
    int maxLength = 0, size = input.size(), prevStart = 0 , currentStart = 0 ;    
    
    for(int i = 1 ; i < size ; ++i)
    {
        if(input[i] != input[i -1])
        {
            //checking if the diff of number is one
            if(input[currentStart] - input[prevStart] == 1)
            {
                // Mark the length as potential result
                maxLength = max(maxLength , i - prevStart);             
            }
            
            prevStart = currentStart;
            currentStart = i;
        }
    }
    // to take care of the last bit 
    return max(maxLength , size - prevStart);
}

Why can the answer not be length 4 ? the sequence 6,6,7,0 ?

#include<iostream>
using namespace std;


void function1(int arr[], int start, int end, int data[], int startD, int endD, bool& done)
{
    if(start<=end+1)
    {
        if(startD == endD && !done)
        {
            int maxV = -10000, minV = INT_MAX;
            for(int i=0;i<endD;i++)
            {
                if(data[i] > maxV)
                    maxV = data[i];
                if(data[i] < minV)
                    minV = data[i];
            }
            if(maxV-minV == 1)
            {
                cout<<"Output :-";
                for(int i=0;i<endD;i++)
                {
                    cout<<" "<<data[i];
                }
                done = true;
                cout<<endl;
            }
        }
        data[startD] = arr[start];
        function1(arr, start+1, end, data, startD+1, endD, done);
        function1(arr, start+1, end, data, startD, endD, done);
    }
}

void function(int arr[], int size)
{
    int data[size];
    bool done = false;
    
    for(int i=size;i>=2 && !done;i--)
        function1(arr, 0, size, data, 0, i, done);
}
    
int main()
{
    int arr[] = {6, 10, 6, 7, 8, 9, 0};
    int size = sizeof(arr)/sizeof(*arr);
    
    function(arr, size-1);
 
    cout<<endl;   
    system("PAUSE");
    return 0;
}