How to Find the Largest Element in an Array
Tags: algorithms, computerscience, cpp, tutorial
Published: 2024-06-03 19:15:41

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**:

```cpp
// Solution-1: Sorting 
// (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**:

```cpp
// Solution-2: Iterative Approach
// (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.

---