Roman C - 8 months ago 67

Java Question

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

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.

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

`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;
}
```