Largest Element In An Array
Difficulty: Easy
Understanding The Problem
Problem Description
Given an array
arr[]
of size
n
, write a program to find the
largest element
in it.
Example 1:
Input: arr[] = [100, 50, 4]
Output: 100
Explanation: 100 is the largest element in the given array.
Solutions
There are various ways to find the largest element. In each programming language, there is support for finding the max in the library. However, internally they work the same. Below are some discussed ways to do that.
- Sorting : Sort the array in ascending order and the last element will be at the last index.
- Traverse : Traverse the array while updating the max value.
You may try this problem here.
1. Sorting
To find the largest element from the array, a simple way is to arrange the elements in ascending order. After sorting, the first element will represent the smallest element, the next element will be the second smallest, and going on, the last element will be the largest element of the array.
Solution Steps
- Sort the array.
- Return the element at the last index of the array.
Pseudo Code
int largestElement(int[] arr, int size) {
// sort the array in ascending order
arr.sort()
largest_element = arr[size-1]
return largest_element
}
Complexity Analysis
Time Complexity: O(n log n)
Space Complexity: O(1)
Critical Ideas To Think
- Why did we return the last element?
- If we would have sorted the array in descending order, then which element we should have returned?
- Sorting the array arranges each and every element and that will help us to find the largest, 2nd largest, 3rd largest elements and so on in constant time. But is it okay to do that much computation here when we just have to find the largest element?
2. Traverse
Take a
max
variable and initialize it with the first element of the array. Now start iterating over the array and whenever a larger element encountered then update the
max
variable otherwise, move forward.
Solution Steps
-
Create a
max
variable and initialize it witharr[0]
-
Iterate from the first
idx
to the lastidx
of the array:
-
If
arr[idx] > max
then updatemax
with arr[idx]
3. Return max
Pseudo Code
int largestElement(int[] arr, int size) {
int max = arr[0]
for(int i = 1 to i < size) {
if(max < arr[i]) {
max = arr[i]
}
}
return max
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
-
Why did we initialize
max
witharr[0]
? -
What if we initialize
max
withINT_MIN
and start the loop from the0th
index. Will that approach would have worked? - What changes do we have to do, when we have to find the 2nd largest element?
Comparison of Solutions
Suggested Problems To Solve
- Find the smallest element of the array
- Find the 2nd largest element of the array
- Find the Kth largest element of the array
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!