Java finding maximum from array time complexity

Question

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]);
        }

Do you have to generate them in ascending order only? If not, you could do a loop with ascending i to get the max for leftArray, then a loop with descending i to get the max for rightArray. — Andy Turner
– Andy Turner, Commented May 16, 2016 at 22:04
@Arctigor O(2n) is the same as O(n) ... Or am I missing something here? — Yassin Hajaj
– Yassin Hajaj, Commented May 16, 2016 at 22:10
@Arctigor indeed, what YassinHajaj said. A constant multiple of O(n) is still O(n). — Andy Turner
– Andy Turner, Commented May 16, 2016 at 22:11

Andy Turner · Accepted Answer · 2016-08-16 15:52:06Z

5

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:

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.

edited Aug 16, 2016 at 15:52

answered May 16, 2016 at 22:23

Andy Turner

141k11 gold badges169 silver badges263 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andy Turner Over a year ago

@Andreas well, ok :) I wasn't counting that one because that's not actually finding the maxes.

Andreas Over a year ago

@AndyTurner You new comment at the end of the answer, combining leftMaxes and printing would however eliminate the need for the leftMaxes array (using running max instead), reducing memory footprint, right?

Andy Turner Over a year ago

@Andreas indeed it would.

Collectives™ on Stack Overflow

Java finding maximum from array time complexity

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related