Problem Statement

Given an array, we have to find the largest element in the array.

Examples

Example 1:

Input: nums = [3, 4, 6, 4, 1]
Output: 6

Explanation: The largest element in nums array is 6.

Example 2:

Input: nums = [-4, -5, -7, 0]
Output: 0

Explanation: The largest element in nums array is 0 being others are negative.

Different Approaches

1️⃣ Sorting

The sorting-based approach involves sorting the array in non-decreasing order and then selecting the last element, which will be the largest one. While this approach guarantees the correct result, it may not be the most efficient for large arrays due to sorting overhead.

Algorithm:

1. Sort the array in non-decreasing order
2. Return the last element of the sorted array, which is the largest.

Code:

#include <iostream>
#include <algorithm> // For std::sort
using namespace std;

int findLargestElement(int arr[], int n) {
    // Sort the array in non-decreasing order
    sort(arr, arr + n);

    // Return the last element of the sorted array, which is the largest
    return arr[n - 1];
}

int main() {
    int arr[] = {12, 45, 78, 23, 56, 91, 34};
    int size = sizeof(arr) / sizeof(arr[0]);

    int largest = findLargestElement(arr, size);
    cout << "The largest element in the array is: " << largest << endl;

    return 0;
}

// Output
The largest element in the array is: 91

Complexity Analysis:

• Time Complexity:
  • The time complexity of the sorting algorithm used (typically quicksort) is O(n logn).
  • Additionally, accessing the last element of the sorted array is constant time, O(1).
  • Therefore, the overall time complexity of this approach is dominated by the sorting step, making it O(n logn).
• Space Complexity:
  • The space complexity of this approach depends on the sorting algorithm used.
  • Typically, sorting algorithms require O(n) auxiliary space for temporary storage.
  • Hence, the space complexity is O(n)

2️⃣ Linear Traversal

The linear traversal approach involves iterating through each element of the array and keeping track of the maximum element encountered so far. This approach is simple to implement and requires only a single traversal of the array.

Algorithm:

1. Initialize a variable max_element to store the maximum element encountered so far.
2. Iterate through each element.
3. For each element, compare it with max_element.
4. If the current element is greater than max_element, update max_element to the current element.
5. Repeat steps 2-4 until the end of the array is reached.
6. At the end of the traversal, max_element will contain the largest element in the array.

Code:

#include <bits/stdc++.h>
 
using namespace std;
int findLargestElement(int arr[], int n) {
 
  int max = arr[0];
  for (int i = 0; i < n; i++) {
    if (max < arr[i]) {
      max = arr[i];
    }
  }
  return max;
}
int main() {
  int arr1[] = {2,5,1,3,0};
  int n = 5;
  int max = findLargestElement(arr1, n);
  cout << "The largest element in the array is: " << max << endl;
 
  int arr2[] =  {8,10,5,7,9};
  n = 5;
  max = findLargestElement(arr2, n);
  cout << "The largest element in the array is: " << max<<endl;
  return 0;
}

Complexity Analysis:

• Time Complexity:O(n), where n is the number of elements in the array.
• Space Complexity:O(1), indicating constant space usage.