Roman C Roman C - 7 months ago 27
Java Question

Find an ascending slice of the array with maximum size

I have a coding test that I have tried to solve.

There's an array with integers like this

int[] A = {2,2,2,2,1,2,-1,2,1,3};


A slice of the array is a pair of integers (P,Q) such that 0 ≤ P ≤ Q < N. Integer P is called the beginning of the slice, integer Q is called ending of the slice. The number Q - P + 1 is called the size of the slice. A slice (P,Q) is called ascending if the corresponding items of the array are in strictly increasing sequence A[P] < A[P+1] <...<A[Q-1] < A[Q].

The slice like (P,P) with only one item is considered to be ascending.

Pair (0,3) is a slice of array A of size 4 that is not ascending. Pair (2,2) is a slice of size 1 that is ascending. Pair (4,5) is a slice of size 2 that is not ascending. Pairs (6,7) and (8,9) are other slices of size 2 that are ascending. There's no more slices in array A that has a size greater than 2 that are ascending.

We need a function that returns the beginning of any ascending slice of array A which has a maximum size. For example the given array should return 4, or 6, or 8.

The following array has three items

int[] A = {30,20,10};


the function may return 0, 1, or 2 because all ascending slices of this array have a size 1;


  • N is an integer within the range [1..300,000];

  • Each element of array A is an integer within the range
    [Integer.MIN_VALUE, Integer.MAX_VALUE]
    ;

  • Array A is not sorted.



Complexity:


  • Expected worst-case time complexity is O(N);

  • Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).



Elements of input array can be modified.

Attempted solution:

public int solution(int[] A) {
int P =0,P1 = 0, Q = 1, max = 0;
int n = A.length;
for (int i = 0; i < n - 2; i++) {
if (A[i] != A[i+1] && A[i] != A[i+2] && A[i+1] != A[i+2]) {
P =P1;
Q = i + 1;
int size = Q - P1 + 1;
if (size > max && isAscending(A, P, Q))
max = size;
P1 = Q;
}
}
return P;
}

boolean isAscending(int[] A, int P, int Q) {
int n = A.length;
for (int i = P; i <= Q; i++) {
if (A[i] >= A[i+1]) return false;
}
return true;
}


For the first array it returns 7 and fails the test, for the second array it passes with 0.

Any help would be greatly appreciated.

Answer

You can start with best solution index = 0 and length = 1.

Set a current ascending slice starting in 0 (current = 0).

Then, loop the array and for each number you can check if it belongs to the current ascending slice or not (A[i - 1] < A[i]).

If not belongs to the current ascending slice, then set your current ascending slice starting in the current index (current = i)

Compare your best solution with the current slice (i - current + 1 > length) and update it if is better.

public int solution(int[] A)
{
    int maxSliceStart = 0;
    int maxSliceLength = 1;

    int currentSliceStart = 0;

    for (int i = 1; i < A.Length; i++)
    {
        if (A[i - 1] >= A[i]) currentSliceStart = i;

        if (i - currentSliceStart + 1 /* length of the current slice */ > maxSliceLength)
        {
            maxSliceStart = currentSliceStart;
            maxSliceLength = i - currentSliceStart + 1;
        }
    }

    return maxSliceStart;
}

EDIT:

If you want ALL slices with the maximum length:

public List<int> solution(int[] A)
{
    List<int> maxSliceStarts = new List<int> { 0 };
    int maxSliceLength = 1;

    int currentSliceStart = 0;

    for (int i = 1; i < A.Length; i++)
    {
        if (A[i - 1] >= A[i]) currentSliceStart = i;

        int currentSliceLength = i - currentSliceStart + 1;

        if (currentSliceLength > maxSliceLength)
        {
            maxSliceStarts.Clear();
            maxSliceLength = currentSliceLength;
        }

        if (currentSliceLength == maxSliceLength)
            maxSliceStarts.Add(currentSliceStart);
    }

    return maxSliceStarts;
}