Find the Largest Element in an Array

Hi everyone, in this article we’ll guide you through the Python program to find the largest element in an Array without Sorting [Problem Link]. Comprehensively with different examples and dry run. So let’s begin.

Examples to understand the program

Example 1
Input: arr = [1, 8, 7, 56, 90]
Output: 90
Explanation: The largest element of the given array is 90.

Input: arr = [5, 5, 5, 5]
Output: 5
Explanation: The largest element of the given array is 5.

Input: arr = [10]
Output: 10
Explanation: There is only one element which is the largest.

Constraints:
1 <= arr.size()<= 10^6
0 <= arr[i] <= 10^6

Also read about the Python Program to Remove duplicates from Sorted array.

1. Brute Force Solution (With Sorting)

This approach uses sorting to solve the problem. While it might not be the most efficient solution, it still gets the job done.

Intuition and Approach

Intuition:

Sorting the array arranges the elements in ascending order, so the largest element will be at the last position after sorting.

Approach:

1. Sort the Array: Sort the array in non-decreasing order. This makes sure that the largest element is placed at the last index of the array.
2. Return the Largest Element: After sorting, the last element in the array is the largest, so return this element.

Code

def largestElement(arr: [], n: int) -> int:
    # Sort the elements first
    arr.sort()

    # Return the largest from the end
    return arr[-1]

Code Explanation

1. Sort the Array:
   • arr.sort(): This line sorts the array arr in ascending order. Sorting rearranges the elements such that the smallest element is at the beginning and the largest element is at the end of the array.
2. Return the Largest Element:
   • return arr[-1]: After sorting, the last element (arr[-1]) is the largest element in the array. This value is returned as the result.

Dry Run

Let’s walk through a step-by-step execution with a sample input:

Edge cases to consider

1. Single Element Array: If the array contains only one element, that element is the largest by default.
2. All Elements Are Identical: If all elements in the array are the same, that element is the largest.
3. Unsorted Input: The input array is not necessarily sorted, so sorting make sure we get the solution.

Time and Space Complexity

1. Time Complexity
   • The time complexity is O(nlog⁡n), where n is the length of the array arr. This is due to the time required to sort the array.
2. Space Complexity:
   • The space complexity is O(1) if we ignore the space required by the sorting algorithm (which may vary depending on the implementation). Our does not use any extra space other than input and output.

2. Optimal Solution (Single Pass Solution)

This approach uses iteration and maintaing the largest number in a variable and returning it.

Intuition and Approach

Intuition:

The idea is to initialize a variable with the first element of the array and then iterate through the array to compare each element with this variable. If any element is larger than the current value, update the variable to this new value. After completing the iteration, the variable will hold the largest element.

Approach:

1. Initialize the Maximum Value: Start by assuming the first element is the largest.
2. Iterate Through the Array: Compare each element with the current maximum value. If a larger element is found, update the maximum value.
3. Return the Largest Element: After completing the iteration, return the value stored in the maximum variable.

Code

def largestElement(arr: [], n: int) -> int:
    max_num = arr[0]
    
    for num in arr:
        if num > max_num:
            max_num = num
    
    return max_num

Code Explanation

1. Initialize the Maximum Value:
   • max_num = arr[0]: This line initializes the max_num variable with the first element of the array. This variable will store the largest element found during the iteration.
2. Iterate Through the Array:
   • for num in arr: This loop goes through each element in the array.
   • if num > max_num: If the current element (num) is greater than max_num, then update max_num to the current element.
3. Return the Largest Element:
   • return max_num: After iterating through the entire array, max_num will contain the largest element, which is then returned.

Dry Run

Let’s walk through a step-by-step execution with a sample input:

Edge cases to consider

1. Single Element Array: If the array contains only one element, that element is the largest by default.
2. All Elements Are Identical: If all elements in the array are the same, the function will correctly return that element.
3. Negative Numbers: Our code should correctly handle arrays with negative numbers, where the largest number is the one closest to zero.

Time and Space Complexity

1. Time Complexity:
   • The time complexity is O(n), where n is the length of the array arr. This is because our code needs to iterate through all elements in the array.
2. Space Complexity:The space complexity is O(1) because the function only uses a constant amount of extra space (for the max_num variable) regardless of the size of the input array.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.