user3215799 user3215799 - 3 months ago 14
Java Question

Java finding maximum from array time complexity

Having an array A of integers with N elements for example {4, 2, 11, -2, 1} i need to find the element with max value from every sub array . Sub arrays are generated this way:

for i = 0, leftArray = {4} , rightArry = {2,11,-2,1}
for i = 1, leftArray = {4,2}, rightArry = {11,-2,1}
for i = 2, leftArray = {4,2,11}, rightArry = {-2, 1}
for i = 3, leftArray = {4,2,11,-2}, rightArry {1}


So, i need something like this:

for (int i = 0; i < A.length; i++){
//LOGIC HERE
System.err.println(String.format("Left array max = %s, Right array max = %s",lmax, rmax));
}


This would't be a problem if we don't care about time-complexity,
BUT expected worst-case time complexity is O(N)

I have not idea how to achive this with O(N) algorithm. Any help would be appreciated.

EDIT:

My current solution:

for (int i = 0; i < A.length; i++)
{
if(i == A.length - 1)
break;

int[] l = Arrays.copyOfRange(A, 0, i + 1);
int[] r = Arrays.copyOfRange(A, i + 1, A.length);

Arrays.sort(l);
Arrays.sort(r);
System.err.println(l[l.length -1] + " " + r[r.length - 1]);
}

Answer

It's possible in O(n), but I can only think of how to do it in two passes to find the maxes, then another pass to print them:

int[] leftMaxes = new int[A.length - 1];
int[] rightMaxes = new int[A.length - 1];

leftMaxes[0] = A[0];
for (int i = 1; i < A.length - 1; ++i) {
  leftMaxes[i] = Math.max(leftMaxes[i-1], A[i]);
}

rightMaxes[A.length - 2] = A[A.length - 1];
for (int i = A.length - 3; i >= 0; --i) {
  rightMaxes[i] = Math.max(rightMaxes[i+1], A[i+1]);
}

for (int i = 0; i < A.length - 1; ++i) {
  System.out.printf("%d: %d %d%n", i, leftMaxes[i], rightMaxes[i]);
}

Ideone demo

Output:

0: 4 11
1: 4 11
2: 11 1
3: 11 1

You could combine the leftMaxes and printing loops (doing the rightMaxes first) to remove one of the passes; but that's not necessary for the required complexity.

And you could combine the rightMaxes and leftMaxes loops, but I think that would make the code a lot harder to read.