Skip to main content

Array Problems

Find Largest Value

Problem statement

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

Test case #1

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

Output: 7

Test case #2

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

Output: 42

Test case #3

Input: A[] = {}

Output: -1

Thought process

This problem never mentioned 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 start 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). To find the largest value, we must travel through all the elements for an unsorted array. 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 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.