Finding the largest element in an array is a common problem that can be approached in different ways. Here, we’ll discuss two methods: one using sorting and the other using an iterative approach.
Solution 1: Sorting
One straightforward method to find the largest element in an array is by sorting the array in ascending order and then selecting the last element.
Implementation:
// (Sort the array in ascending order & get the last element)
// Time Complexity: O(nlogn)
// Space Complexity: O(1)
int findLargestElement(vector<int> &arr)
{
sort(arr.begin(), arr.end());
// Return the last element of the sorted array
return arr[arr.size() – 1];
}
Logic:
1. Sort the array: Use the sort function to sort the array in ascending order.
2. Return the last element: The largest element will be the last element in the sorted array.
Time Complexity: O(n log n)
Explanation: The time complexity is dominated by the sorting algorithm.
Space Complexity: O(1)
Explanation: Sorting is done in place, so no additional space is used.
Example:
Input: arr = [10, 20, 5, 3, 100]
Output: 100
Explanation: The sorted array is [3, 5, 10, 20, 100] and the last element is 100.
Solution 2: Iterative Approach
A more efficient method is to iterate through the array while keeping track of the maximum element found so far.
Implementation:
// (Using a max variable)
// Time Complexity: O(n)
// Space Complexity: O(1)
int findLargestElement(vector<int> &arr, int n)
{
int max = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
Logic:
1. Initialize max variable: Set max to the first element of the array.
2. Iterate through the array: Compare each element with max.
3. Update max: If the current element is greater than max, update max with the current element.
4. Return max: After completing the iteration, max holds the largest element.
Time Complexity: O(n)
Explanation: The array is traversed once.
Space Complexity: O(1)
Explanation: Only a constant amount of extra space is used.
Example:
Input: arr = [10, 20, 5, 3, 100]
Output: 100
Explanation: The largest element found during the iteration is 100.
Comparison
Sorting Method:
Pros: Simple and easy to implement.
Cons: Less efficient due to the O(n log n) time complexity.
Use Case: Suitable when sorting the array is required for other purposes.
Iterative Method:
Pros: More efficient with O(n) time complexity.
Cons: Slightly more complex logic.
Use Case: Ideal for finding the largest element when sorting is not needed.
Edge Cases
Empty Array: If the array is empty, the function should handle it by returning an appropriate value or throwing an exception.
Single Element Array: If the array contains only one element, that element is the largest by default.
All Elements Same: If all elements in the array are the same, the function should correctly return that element as the largest.
Additional Notes
Stability: Since we are only finding the largest element, stability (preserving the order of equal elements) is not relevant.
Efficiency: The iterative approach is more efficient for large datasets compared to the sorting method.
Use Cases: The iterative method is generally preferred for its O(n) time complexity and O(1) space complexity, making it suitable for large datasets.
Conclusion
Both methods are effective for finding the largest element in an array but the iterative approach is more efficient in terms of time complexity. Understanding both approaches provides valuable insights into different problem-solving strategies and their trade-offs.
