-2
\$\begingroup\$

Largest element in an array's most optimal approach. The code I have written has passed all test cases in https://www.naukri.com/code360/problems/largest-element-in-the-array-largest-element-in-the-array_5026279, and it computes in O(logN) time. Are there any mistakes here? And I cannot find any solutions that exists in LogN time computation. Is there any edge cases to this?

static int largestElement(int[] arr, int n) {
    // Write your code here.
    int max = arr[0];
    int i = 1;
    int j = n-1;
    while(i<=j){
        if(arr[i]>=max  && arr[i] >= arr[j]) max = arr[i];
        else if(arr[j]>=max  && arr[j] >= arr[i]) max = arr[j];
        i++;
        j--;
    }
    return max;
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Java? C#? Something else? \$\endgroup\$
    – Reinderien
    Commented Apr 18 at 12:24
  • 7
    \$\begingroup\$ This isn't O(log(n)). It is O(n). \$\endgroup\$
    – slepic
    Commented Apr 18 at 12:44

1 Answer 1

1
\$\begingroup\$

linear algorithm

The OP code does not complete in \$O(\log n)\$ logarithmic time.

In general a correct algorithm will have at least \$O(n)\$ linear complexity. It cannot do better than that, since the maximum element could be hiding at any position.

code

This line of source code is correct:

    int max = arr[0];

In particular, initializing in this way is better than using a \$- \infty\$ sentinel such as \$-(2^{63})\$.

The remainder of the code should be rewritten, as a short loop.

(When initially reading it, I was kind of hoping that assignment would immediately produce the answer in \$O(1)\$ constant time by virtue of input being in monotonic decreasing sorted order, but then I saw the problem puts no constraint on the input vector.)

Please delete that "Write your code here" comment line.

Just write a linear scan of the input integers, and you're done. No need to approach it from both ends -- ascending indexes will suffice.

braces

        if(arr[i]>=max  && arr[i] >= arr[j]) max = arr[i];

Please don't do that. Surround if / else statements with { } braces, even if there's only a single statement as we see here.

The way the OP code is phrased, it invites maintenance headaches down the road. We don't want some hapless engineer to add a second statement and mispredict how the compiled code will behave.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.