Find Largest Value In an Array

Problem statement

Given an array A[] of size N, find the largest element in the given array. If the array is empty return -1.

Examples

Example #01:

Input: A[] = {2, 1, 4, 7, 3}

Output: 7

Example #02:

Input: A[] = {10, -10, 4, 7, 8, 42}

Output: 42

Example #03:

Input: A[] = {}

Output: -1

Thought process

This problem never mentioned anything about sorted or unsorted input. Let's say the interviewer didn't reveal whether the input is sorted or unsorted. It is your responsibility to ask the interviewer and get clarification before you run down to solving the problem.

As the solution totally changes for a sorted & unsorted array.

For a sorted array, the largest element is at the last index, and you can return the answer as:

A[A.length - 1];

Let's walk through the unsorted array algorithm.

Optimal approach

Algorithm

1. Create a variable max and store the first element of the array max = A[0].
2. Now, iterate through all of the array elements starting from index 1.
3. Compare the max value with each A[i].
4. If A[i] > max, update max = A[i].
5. Once the loop finishes, return the max.

Solution

This is an optimal solution to find the largest element in an array.

public class FindLargestValue {
  public static void main(String[] args) {
    int[] A = {10, -10, 4, 7, 8, 42};

    System.out.println(findLargestValue(A));
  }

  private static int findLargestValue(int[] A) {
    if (A.length == 0) {
      return -1;
    }
    if (A.length == 1) {
      return A[A.length - 1];
    }

    int max = A[0];

    for (int i = 1; i < A.length; i += 1) {
      if (A[i] > max) {
        max = A[i];
      }
    }

    return max;
  }
}

Complexity analysis

Time complexity: O(n). We need to travel through all the elements for an unsorted array to find the largest value. So if n is the length of the input array, then O(n) is the total time taken for this algorithm.

Space complexity: O(1), no extra space is used for this algorithm.

Sorting array (not recommended)

Sorting an array takes O(nlogn) time. So this approach is not recommended.

Solution

import java.util.Arrays;

public class FindLargestValue {
  public static void main(String[] args) {
    int[] A = {10, -10, 4, 7, 8, 42};

    System.out.println(sorting(A));
  }

  private static int sorting(int[] A) {
    Arrays.sort(A);
    return A[A.length - 1];
  }
}

Complexity analysis

Time complexity: O(nlogn). Sorting takes O(nlogn), and A[A.length - 1] is a constant operation. So overall, the time complexity of the above algorithm is O(nlogn).

Space complexity: O(1), no extra space is used for this algorithm.