Program to Find Largest Element in an Array

Problem Statement

You are given an array arr[] of size N, where N represents the number of elements in the array. The task is to write a program to find and determine the largest element within this array.

Examples

Example 1:

Example 2:

Example 3:

Example Explanation

In above all the examples, we are finding the largest element from the array. The array might contain a negative element.

Constraints

You are provided with an array arr[] of size N. Your objective is to identify the largest element within this given array.

Approach 1 - Iterative Approach

The iterative approach involves traversing through the array and keeping track of the largest element encountered so far. As you iterate through each element, compare it with the current largest element. If the current element is greater than the current largest element, update the largest element to the current element.

Algorithm:

1. Initialize a variable max_element with a value of negative infinity. This will serve as the placeholder for the largest element.
2. Iterate through each element num in the array arr[]:
   • If num is greater than max_element, update max_element to the value of num.
3. After iterating through the entire array, the variable max_element will hold the largest element.

Code Implementation

Below is the implementation of the above approach in different programming languages:

C Programming Language:

Output:

Explanation:

• The function findLargestElement takes an array arr and its size N as parameters and returns the largest element in the array.
• We start by initializing maxElement to INT_MIN, which represents the smallest possible integer value.
• The for loop iterates through each element in the array. For each element, it checks if the element is greater than the current maxElement. If it is, the value of maxElement is updated with the current element.
• After iterating through the entire array, the function returns the maxElement, which will be the largest value encountered.
• In the main function, we read the size of the array and its elements from the user. Then, we call the findLargestElement function to obtain the largest element and print it.

C++ Programming Language:

Output:

Explanation:

• After iterating through the entire array, the function returns the maxElement, which will be the largest value encountered.
• In the main function, we read the size of the array and its elements using std::cin. Then, we call the findLargestElement function to obtain the largest element and print it using std::cout.

JAVA Programming Language:

Output:

Explanation:

• After iterating through the entire array, the method returns the maxElement, which will be the largest value encountered.
• In the main method, we use a Scanner to read the size of the array and its elements from the user. Then, we call the findLargestElement method to obtain the largest element and print it.

Python Programming Language:

Output:

Explanation:

• We start by initializing max_element to negative infinity, ensuring that any element in the array will be greater than this initial value.
• Then, we loop through each element in the array. For each element, we compare it with the current max_element. If the element is greater, we update max_element with the value of the current element.
• By the end of the loop, max_element will contain the largest value encountered in the array.

Time Complexity

This approach requires iterating through the entire array once, resulting in a time complexity of $O(N)$, where N is the size of the array.

Space Complexity

The approach uses a constant amount of extra space, regardless of the input size, leading to a space complexity of $O(1)$.

Approach 2 - Recursive Approach

The recursive approach involves breaking down the problem of finding the largest element in an array into smaller subproblems. In this case, we can break down the array into two parts: the first element and the rest of the array. The largest element in the entire array can then be determined by comparing the first element with the largest element in the rest of the array.

Algorithm

• If the array has only one element, return that element as the largest.
• Otherwise, divide the array into two parts: the first element (arr[0]) and the rest of the array (arr[1:]).
• Recursively find the largest element in the rest of the array by calling the function with the smaller array (arr[1:]).
• Compare the first element (arr[0]) with the result obtained from the recursive call.
• Return the larger of the two elements as the result.

Code Implementation

Below is the implementation of the above approach in different programming languages:

C Programming Language:

Output:

Explanation:

• Every step is similar to the steps followed in the above code.
• The function compares the first element arr[0] with the result of the recursive call restMax. It returns the larger of the two elements using the ternary conditional operator (? :).

C++ Programming Language:

Output:

Explanation:

• Every step is similar like the steps followed in the above code.

Java:

Output:

Explanation:

• Every step is similar to the steps followed in the above code.
• The method returns the larger of the first element arr[0] and the result of the recursive call using the Math.max function.

Python:

Output:

Explanation:

• The recursive function find_largest_recursive takes an array arr and its size n as parameters and returns the largest element in the array.
• If the array has only one element n == 1, the function directly returns that element as it is the largest in this case.
• Otherwise, the array is divided into two parts: the first element arr[0] and the rest of the array arr[1:].
• The function recursively calls itself with the smaller array arr[1:] and compares the first element with the result of the recursive call rest_max.
• The function then returns the larger of the two elements arr[0] and rest_max as the largest element.

Time Complexity

The recursion breaks down the problem into smaller subproblems, but each element is visited once, resulting in a time complexity of $O(N)$, where N is the size of the array.

Space Complexity

The recursive calls consume memory on the call stack, leading to a space complexity of $O(N)$ due to the depth of the recursion.

Approach 3 - Using Library Function

This approach involves utilizing a built-in or library function provided by the programming language to directly find the largest element in an array. Many programming languages offer standard library functions that can efficiently solve this problem without the need for manual traversal and comparison.

Algorithm

Identify the appropriate library function provided by the programming language for finding the maximum element in an array.

Code Implementation

C:

Output:

Explanation:

• The qsort() function in C is used to sort an array in ascending order. We need to provide a comparator function that defines how the elements should be compared during sorting.
• The qsort() function is then used to sort the array in ascending order. After sorting, the largest element will be the last element of the sorted array.
• We print the largest element as the result.

C++:

Output:

Explanation:

• The std::max_element() function is used to find the iterator pointing to the largest element in the array.
• We dereference the iterator to get the actual largest value and print it as the result.

JAVA:

Output:

Explanation:

• The Collections.max() method in Java is used to find the maximum element in a collection (such as an ArrayList) or an array.
• We use an ArrayList<Integer> to store the elements entered by the user.
• The Collections.max() method is then used to find the largest element in the ArrayList.
• We print the largest element as the result.

Python:

Output:

Explanation:

• The max() function in Python returns the largest element from an iterable, such as a list or an array.
• The elements are split and converted into a list using the split() function and the map() function with int to convert them into integers.
• We then use the max() function to find the largest element in the array and print the result.

Time Complexity

The time complexity of the library function depends on its implementation and efficiency, which can vary across programming languages. However, these library functions are often optimized for performance and can achieve $O(N)$ time complexity.

Space Complexity

The space complexity for this approach is minimal, often $O(1)$, as it does not involve additional memory usage proportional to the input size.

Approach 4 - Using Pointers

This approach involves utilizing pointers in languages that support them, such as C and C++, to traverse the array and identify the largest element. By maintaining a pointer that points to the largest element encountered so far, we can compare each element with the value pointed to by the pointer and update it as needed.

Algorithm:

• Initialize a pointer maxPtr to the first element of the array.
• Iterate through the array using a loop and a pointer currentPtr that starts from the second element.
• If the value pointed to by currentPtr is greater than the value pointed to by maxPtr, update maxPtr to point to currentPtr.
• After the loop, the value pointed to by maxPtr is the largest element in the array.

Code Implementation

Here's an example using C++:

Output:

Explanation:

• We iterate through the array using a loop, starting from the second element. For each element, we compare it with the value pointed to by maxPtr. If the element is greater, we update maxPtr to the current element.
• At the end, the value pointed to by maxPtr is the largest element in the array.

Time Complexity

The time complexity of this approach is $O(N)$, where N is the size of the array.

Space complexity

The space complexity of this approach is $O(1)$, which is constant.