CareerCup

Should be O(n), but I don't have c++11 handy so no hash table

void Longest1Subset(int* pArr, int sz)
{
   std::map<int, int> counts; //should be hash table for O(n)
   for (int i = 0; i < sz; i++)
   {
       counts[pArr[i]]++; 
       counts[pArr[i]-1]++;
       printf("%d,", pArr[i]);
   }
   std::pair<int,int> res(0,0);
   for (std::map<int,int>::iterator i = counts.begin(); i != counts.end(); i++)
      res = res.second > i->second ? res : *i;
   printf(" => (%d to %d): %d\n", res.first, res.first+1, res.second);
}

int main()
{
   int test1[] = {1,5,1,0,2,6,2,1};
   int test2[] = {6,6,5,5,4,4,3,3,2,2,2,1,0,7,7,7,7};
   int test3[] = {0,0,-1,-1,-9,9,-9,9,-9,9,-9,-10,9};
   Longest1Subset(test1, sizeof(test1)/sizeof(*test1));
   Longest1Subset(test2, sizeof(test2)/sizeof(*test2));
   Longest1Subset(test3, sizeof(test3)/sizeof(*test3));
   getch();
}

This algorithm output is either the number with the max count or the sum of a pair which difference is one.

This algorithm has an order to growth of O(n) using a single pass through the array.

public static List<int> FindMaxSubset(int[] set)
{
	List<int> result = new List<int>();
	if(set == null || set.Count == 0)
	{
		return result;
	}
	
	Dictionary<int, int> numberCount = new Dictionary<int, int>();

	// This is to calculate the max value which diference is 0 which is itself
	int maxItem = set[0];
	int maxItemCount = 1;

	// Finds the best out of the combination of two numbers with difference of 1
	int twoItem1 = set[0];
	int twoItem2 = set[0];
	int twoItemMaxCount = 0;
	foreach(int s in set)
	{
		if(!numberCount.ContainsKey(s))
		{
			numberCount.Add(s, 1);
		}
		else
		{
			numberCount[s]++;
		}
	
		// Track the max count of an item
		if(maxCount < number[s])
		{
			maxItem = s;
			maxCount = numberCount[s];
		}

		// Check if an equivalent sum exist
		if(numberCount.ContainsKey(s -1))
		{
			int count = numberCount[s] + numberCount[s - 1];
			if(twoItemMaxCount < count)
			{
				twoItem1 = s;
				twoItem2 = s - 1;
				twoItemMaxCount = count;
			}
		}
		else if(numberCount.ContainsKey(s + 1))
		{
			int count = numberCount[s] + numberCount[s + 1];
			if(twoItemMaxCount < count)
			{
				twoItem1  = s;
				twoItem2 = s + 1;
				twoItemMaxCount = count;
			}
		}
	}

	// Determine which one is the maximum out of:
	//	A single element max count or
	// 	The two item sum count
	if(maxCount > twoItemMaxCount)
	{
		for(int i = 0; i < maxCount; i++)
		{
			result.Add(maxItem);
		}
	}
	else
	{
		int count = numberCount[twoItem1];
		for(int i = 0; i < count; i++)
		{
			result.Add(twoItem1);
		}
		
		count = numberCount[twoItem2];
		for(int i = 0; i < count; i++)
		{
			result.Add(twoItem2);
		}
	}

	return result;
}

It is clear, that the resulting subset must contain one or two consequetive numbers from the list. Having this idea, let's count the number of times every number occurs in the list. (we can use HashMap for this purpose). Now, let's iterate over possible keys in map and calculate the answer.

for(int i = 0; i < a.length; ++i) {
  if (!map.containsKey(a[i])) map.put(a[i], 0);
  map.put(a[i], map.get(a[i]) + 1);
}
int ret = 0;
for(int key in map.keySet()){
  ret = Math.max(ret, map.get(key));
  if (map.containsKey(key-1)) ret = Math.max(ret, map.get(key) + map.get(key - 1));
  if (map.containsKey(key + 1)) ret = Math.max(ret, map.get(key) + map.get(key + 1));
}

System.out.println(ret);

Here is my solution without extraspace and O(n) running time.

The idea is you scan through the array and change the minimum and check if the difference is with -1 -> 0 -> 1. If the difference is greater than 1 you can safely skip through until you reach the maximum number at which point you repeat the same process.

I could probably do away with couple variables.

private static void printSubset(int[] a)
    {
    	int size = a.length;
    	int sequenceStart = 0, sequenceEnd = 0;
    	int finalSequenceStart = 0, finalSequenceEnd = -1;
    	int min = a[0],max = a[0];
    	
    	for(int j = 0;j< size; j++)
    	{
    		if((a[j]-min <= 1) && (a[j] - min >= -1))
    		{
    			sequenceEnd = j;
    			if(a[j] < min)
    				min = a[j];
    			if((finalSequenceEnd-finalSequenceStart)< (sequenceEnd-sequenceStart))
    			{
    				finalSequenceEnd = sequenceEnd;
    				finalSequenceStart = sequenceStart;
    			}
    			
    		}
    		else
    		{
    			min = a[j];
    			max = a[j];
    			sequenceStart = j;
    			sequenceEnd = j;
    		}
    	}
    	
    	System.out.println("Sequence Start is: "+finalSequenceStart+" Sequence End is:" +finalSequenceEnd);
    	
    }

Is this a modified version of LIS problem?

Is this a modified version of LIS problem?

For every size of subsequence (window) starting from the whole list and decreasing in size slide the window and remove the element exited the window from the ht and insert the one that entered the window on ht. Insertions and deletions in the ht are log(n)

public static List<int> FindLongestSubstring(List<int> list){
		if(list == null || list.Count<=1) return list;
		//keys are elements from the list and values are the number of times they appear in the current window
		SortedDictionary<int,int> bst = new SortedDictionary<int,int>();
		
		int windowSize = list.Count, offset = 0;
		for(; windowSize >= 2 ; --windowSize){
			bst.Clear();
			for(int j = 0 ; j < windowSize ; ++j){
				int v = list[j];
				if(bst.ContainsKey(v))
					bst[v]++;
				else
					bst[v] = 1;
			}
			for(offset = 0; windowSize + offset < list.Count() ; ++offset)
			{
				if(offset>0){
					int outValue = list[offset-1];
					int inValue = list[offset+windowSize-1];

					if(--bst[outValue] == 0){
						bst.Remove(outValue);
					}
					if(bst.ContainsKey(inValue))
						bst[inValue]++;
					else
						bst[inValue] = 1;
				}
					
				if(bst.Keys.Last() - bst.Keys.First() <= 1 ){
					return list.GetRange(offset,windowSize);
				}
			}
		}
		
		//any single element is a valid solution
		return new List<int>{list[0]};
		
	}

Java solution below in O(n) time.

1. Build a HashMap containing count of how many times each number appears in the array.

2. Then loop through the map to get highest count for pairs of ints i and i - 1.

3. Build the return array by looping through original array and finding ints matching pair found in step 2.

public static Integer[] longestSubset(Integer[] intArray) {
		Map<Integer, Integer> intCounts = new HashMap<Integer, Integer>();
		Integer[] longestPair = new Integer[] {null, null};
		Integer longestCount = 0;
		
		for (Integer i : intArray) {
			intCounts.put(i, intCounts.containsKey(i) ? intCounts.get(i) + 1 : 1);
		}
		
		for (Integer i : intCounts.keySet()) {
			Integer thisCount = intCounts.get(i);
			boolean neighbourInSet = intCounts.containsKey(i - 1);
			
			if (neighbourInSet) 
				thisCount = thisCount + intCounts.get(i - 1);
			
			if (thisCount > longestCount) {
				longestCount = thisCount;
				longestPair[0] = neighbourInSet ? i - 1 : null;
				longestPair[1] = i;
			}
		}
		
		Integer[] returnArray = new Integer[longestCount];
		Integer currentReturnIndex = 0;
		
		for (Integer i : intArray) {
			if (longestPair[0] == i || longestPair[1] == i) {
				returnArray[currentReturnIndex++] = i;
			}
		}
		
		return returnArray;
	}

There's a simple O(n²) solution which is O(1) in space.

int longestSubset(int[] array) {
    int min, max, longest = 0;
    for (int i=0; i < array.length; i++) {
        min = array[i];
        max = array[i];
        for (int j=i+1; j < array.length; j++) {
            if (array[j] < min)
                min = array[j]
            else if (array[j] > max)
                max = array[j]

            if (max - min <= 1 && (j - i) + 1 > longest)
                longest = (j - i) + 1;
        }
    }
    return longest;
}

Can anybody good at analysing complexity take a look in the C# code bellow. I understand it's o(n^2) in the worst case. Is there a way to estimate the average complexity? Suggestions for a good read on complexity?anyone?

using System;
using System.Collections.Generic;
using System.Linq;
public class Program	
{
	public static List<int> FindLongestSubstring(List<int> list){
		if(list == null || list.Count<=1) return list;
		//keys are elements from the list and values are the number of times they appear in the current window
		Dictionary<int,int> bst = new Dictionary<int,int>();
		for(int j = 0 ; j < list.Count ; ++j){
			int v = list[j];
			if(bst.ContainsKey(v))
				bst[v]++;
			else
				bst[v] = 1;
		}
		
		int N = list.Count;
		int windowSize = N, offset, outValue, inValue;
		while(windowSize >= 2){

			//Current window size make a pass from left->right
			for(offset = 0; windowSize + offset <= N ; ++offset)
			{
				if(offset>0){
					outValue = list[offset-1];
					inValue = list[offset+windowSize-1];
					if(--bst[outValue] == 0){
						bst.Remove(outValue);
					}
					if(bst.ContainsKey(inValue))
						bst[inValue]++;
					else
						bst[inValue] = 1;
				}
				if(bst.Keys.Count <=2 && Math.Abs(bst.Keys.Last() - bst.Keys.First()) <= 1 ){
					return list.GetRange(offset, windowSize);
				}
					
			}

			outValue = list[N - windowSize];
			if(--bst[outValue] == 0){
				bst.Remove(outValue);
			}
			--windowSize;

			//Make a pass right->left
			for(offset = 0; windowSize + offset <= N ; ++offset)
			{
				if(offset>0){
					outValue = list[N - offset];
					inValue = list[N-(offset+windowSize)];
					if(--bst[outValue] == 0){
						bst.Remove(outValue);
					}
					if(bst.ContainsKey(inValue))
						bst[inValue]++;
					else
						bst[inValue] = 1;
				}
				if(bst.Keys.Count <=2 && Math.Abs(bst.Keys.Last() - bst.Keys.First()) <= 1  ){
					return list.GetRange(N - windowSize - offset, windowSize);
				}
			}
			
			outValue = list[windowSize-1];
			if(--bst[outValue] == 0){
				bst.Remove(outValue);
			}

			--windowSize;
			
		}
		
		//any single element is a valid solution
		return new List<int>{list[0]};
		
	}
	public static void Main()
	{
		var list = new List<int>(new[]{1,2,1,2,3,4,2,2,2,2,1,1,2,3,4,5,5,4,5,4,5,5,5,5,5,6,6,6,6,6});
		//list = new List<int>(new []{1, 5, 6, 6, 6, 7, 7, 9});
		
		var res = FindLongestSubstring(list);
		res.Dump();
		Console.WriteLine(res.Count);
		Console.WriteLine("Hello World");
	}
}

Here is an o(n) solution.

The idea is to iterate through the array and update the buckets the array value could go in to. arr[i] could go in to two buckets primarily - one whose minValue is arr[i] itself and the other whose minValue is arr[i]-1 (to ensure the differences between elements in a bucket do not differ by 1).

int FindLongestSubset(int[] arr)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>();
//Key - minimum value of a set
//Value - count of occurrences of min value and the minvalue+1
int longestSubsetSequence;

for(int i=0; i<arr.length; i++)
{
//arr[i] value can go in to dictionary whose min value is arr[i] or arr[i]-1, so we update both the dictionary entries

int result1;
if(!dictionary.KeyExists(arr[i]))
{
dictionary.Add(arr[i], 1);
result1=1;
}
else
{
dictionary[arr[i]] = dictionary[arr[i]] + 1;
result1 = dictionary[arr[i]];
}

int result2;
if(!dictionary.KeyExists(arr[i]-1))
{
result2 = 1;
dictionary.Add(arr[i]-1, 1);
}
else
{
dictionary[arr[i]-1] = dictionary[arr[i]-1] + 1;
result2 = dictionary[arr[i]-1];
}
int maxLocalResult = max(result1, result2);
if(maxLocalResult > longestSubsetSequence)
{ longestSubsetSequence = maxLocalResult; }
}

return longestSubsetSequence;
}

Here is my solution, simple and concise O(n) time, O(1) space, the basic idea is to iterate the array comparing for difference of 1 values and treating the special case diff 2, in a sliding window fashion:

public static int[] findLongestSubsetDiff1(int[] a){		
		int i = 0, j = 0, diff = 0;
		int longest = 1, minLongestIndex = 0, min = a[0], max = a[0], minIndex = 0, maxIndex = 0, newLongest = 0;
		
		for(i=1; i < a.length; i++) {
			max = Math.max(a[i], max);
			min = Math.min(min, a[i]);
			
			diff = Math.abs(max - min);			
			if (diff == 1 || diff == 0) {
				maxIndex = i;
				newLongest = (maxIndex - minIndex) + 1;
				if (longest < newLongest) {
					longest = newLongest;
					minLongestIndex = minIndex; 
				}												
				
			} else if (diff == 2) {				
				minIndex = minLongestIndex + 1;
				min = a[minIndex];			
				maxIndex = i;
				max = a[i];
				diff = Math.abs(max - min);					
				
				while (diff == 2 && minIndex < maxIndex) {
					minIndex++;
					min = a[minIndex];			
					diff = Math.abs(a[i] - min);					
				}

				max = Math.max(max, min);
			}	
			else {
				min = max = a[i];
				minIndex = maxIndex = i;				
			}						
		}
		
		int[] r = new int[longest];									
		for(j=0, i = minLongestIndex; i < a.length && j < longest; i++, j++) {
			r[j] = a[i];	
		}
		
		return r;				
	}

public static void main(String[] args)
  {
    System.out.println(maxLen(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0));
  }

  public static int maxLen(int min, int max, int len, int index)
  {
    if (index >= arr.length && Math.abs(max - min) != 1)
    {
      return Integer.MIN_VALUE;
    }
    if (index >= arr.length && Math.abs(max - min) == 1)
    {
      return len;
    }
    int orgMax = max;
    int orgMin = min;
    if (arr[index] <= min)
      min = arr[index];
    if (arr[index] >= max)
      max = arr[index];
    int p = maxLen(min, max, len + 1, index + 1);
    int q = maxLen(orgMin, orgMax, len, index + 1);
    return Math.max(p, q);
  }

public static void main(String[] args)
  {
    System.out.println(maxLen(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0));
  }

  public static int maxLen(int min, int max, int len, int index)
  {
    if (index >= arr.length && Math.abs(max - min) != 1)
    {
      return Integer.MIN_VALUE;
    }
    if (index >= arr.length && Math.abs(max - min) == 1)
    {
      return len;
    }
    int orgMax = max;
    int orgMin = min;
    if (arr[index] <= min)
      min = arr[index];
    if (arr[index] >= max)
      max = arr[index];
    int p = maxLen(min, max, len + 1, index + 1);
    int q = maxLen(orgMin, orgMax, len, index + 1);
    return Math.max(p, q);
  }

public static void main(String[] args)
  {
    System.out.println(maxLen(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 0));
  }

  public static int maxLen(int min, int max, int len, int index)
  {
    if (index >= arr.length && Math.abs(max - min) != 1)
    {
      return Integer.MIN_VALUE;
    }
    if (index >= arr.length && Math.abs(max - min) == 1)
    {
      return len;
    }
    int orgMax = max;
    int orgMin = min;
    if (arr[index] <= min)
      min = arr[index];
    if (arr[index] >= max)
      max = arr[index];
    int p = maxLen(min, max, len + 1, index + 1);
    int q = maxLen(orgMin, orgMax, len, index + 1);
    return Math.max(p, q);
  }

#include    <iostream>
#include    <algorithm>
#include    <unordered_map>
using namespace std;

void find(int a[],int n,int &s,int &l)
{
    unordered_map<int,int> m;
    for(int i=0;i<n;i++) {
        m[ a[i] ]++;
    }
    int max1 = 0;
    int cur = 0;
    int first;
    for(auto i : m) {
        cur = i.second + m[i.first+1];
        if(cur > max1) {
            s = i.first;
            max1 = cur;
        }
    }
    l = max1;
}
int main()
{
    //int a[] = { 2, 6, 7, 9, 1, 0, 1, 2, 3, 6 };
    //int a[] = {1,5,1,0,2,6,2,1};
    int a[] = {6,6,5,5,4,4,3,3,2,2,2,1,0,7,7,7,7};
    //int a[]=  {0,0,-1,-1,-9,9,-9,9,-9,9,-9,-10,9};
    int n = sizeof(a)/sizeof(a[0]);
    int s,l;
    find(a,n,s,l);
    cout<<"from "<<s<<" to "<<(s+1)<<" : "<<l<<endl;
    cout<<endl;
    return 0;
}