Thursday, May 23, 2013

Given an int array which might contain duplicates, find if it is a sequence.

Given an int array which might contain duplicates, find if it is a sequence.
Eg. {45,50,47,46,49,48}
is a sequence 45, 46,47,48,49,50
Sorting is an obvious solution. Can this be done in O(n) time and O(1) space

                                            (Or)
Write a method that takes an int array of size m, and returns (True/False) if the array consists of the numbers n...n+m-1, all numbers in that range and only numbers in that range. The array is not guaranteed to be sorted. (For instance, {2,3,4} would return true. {1,3,1} would return false, {1,2,4} would return false.

By working with a[i] % a.length instead of a[i] you reduce the problem to needing to determine that you've got the numbers 0 to a.length - 1.

Approach:
Example array: A = {4, 1, 3, 3, 2}
1. get the min and max.
min=1 and max=4
2. if (max - min) > A.length then "its NOT a sequence".
3. else for each element in A[i] do the following:
a. calculate A[i] - min till A[i]-min=i;
i=0; 4 - 1 = 3, swap A[0] and A[3]
Now we have A = {3, 1, 3, 4, 2}
Again,
i=0; 3 - 1 = 2, now A[0] and A[2] are same so swap A[0] and A[length-1] and put A[length] = infinite.
A = {2, 1, 3, 4, INF}
Again,
i=0; 2 - 1 = 1, swap A[0] and A[1],
A = {1, 2, 3, 4, INF}
i=1; 2 - 1 = 1 (which is same as i)
similarlty for i=2, i=3
finally we have A as,
A = {1, 2, 3, 4, INF}

public static boolean isSequence(int A[])
{
int min = Integer.MINIMUM;
int max = Integer.MAXIMUM;
int len = A.length;
for(int i=0;i<len;i++)
{
if(A[i] < min)
{
min = A[i];
}else if(A[i] > max)
{
max = A[i];
}
}

if(max-min > A.length)
return false;

int i=0;
while(i<len)
{
while(i<len && i != (A[i] - min))
{
if(A[A[i] - min] == A[i])
{
A[i] = A[len-1] ;
A[len-1] = Integer.MAXIMUM;
len = len-1;
}else
{
int k = A[i] - min;
int temp= A[i];
A[i] = A[k];
A[k] = temp;
}

}

i++;

}

for(int i=1;i<len;i++)
{
if((A[i] - A[i-1]) != -1
return false;
}

return true;
}

No comments: