Find Largest Value In an Array
In this lesson, you will learn how to approach the problem, and come up with different strategies to solve the problem.
Table of Contents
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
- Create a variable
max
and store the first element of the arraymax = A[0]
. - Now, iterate through all of the array elements starting from index
1
. - Compare the
max
value with eachA[i]
. - If
A[i] > max
, updatemax = A[i]
. - 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.
👨🏻💻 Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.