##### 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

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 class ArraySeq {

public static void main(String[] args) {

int[] A = { 45, 50, 47, 45, 50, 46, 49, 48, 49 };

System.out.println("Printing Original Array ...");

printArr(A);

System.out.println("Is Sequence: " + isSequence(A));

}

public static boolean isSequence(int[] A) {

int len = A.length;

int MIN = Integer.MAX_VALUE;

int MAX = Integer.MIN_VALUE;

boolean result = false;

for (int i = 0; i < len; i++) {

if (A[i] < MIN) {

MIN = A[i];

}

if (A[i] > MAX) {

MAX = A[i];

}

}

System.out.println("MIN:" + MIN + " " + "MAX:" + MAX);

if ((MAX - MIN) >= len) {

return result;

}

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.MAX_VALUE;

len = len - 1;

} else {

int k = A[i] - MIN;

int temp = A[i];

A[i] = A[k];

A[k] = temp;

}

}

++i;

}

System.out.println("Final Array ... ");

printArr(A);

for (i = 1; i < len; i++) {

if ((A[i] - A[i - 1]) != 1) {

return false;

}

}

return true;

}

public static void printArr(int[] A) {

int len = A.length;

for (int i = 0; i < len; i++) {

System.out.print(A[i] + " ");

}

System.out.println();

}

}

## No comments:

Post a Comment