Lesson

4.4Find largest no in the array

Finding the Greatest Element in an Array

Problem Statement

Given an array of integers, find the greatest (maximum) element in the array.

Example

Approaches

Brute Force Approach

Idea: Iterate through the array and keep track of the maximum element found so far.
Steps:
1. Initialize a variable maxElement with the first element of the array.
2. Iterate through the array starting from the second element.
3. For each element, compare it with maxElement.
4. If the element is greater than maxElement, update maxElement.
5. Return maxElement at the end.
Time Complexity: O(n) - We need to traverse all elements in the array.
Space Complexity: O(1) - No extra space is required, just a variable to store the maximum.
Example:

Final Output: 12

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 5
2. Input: [5, 4, 3, 2, 1] | Output: 5
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -1
4. Input: [100] | Output: 100
5. Input: [] | Output: undefined (Empty Array)

2. Using JavaScript's Built-in Function

Idea: Use JavaScript's built-in Math.max() function along with the spread operator to find the maximum element.
Steps:
1. Simply return Math.max(...array).
Time Complexity: O(n) - Internally, Math.max() also traverses the entire array.
Space Complexity: O(1) - No extra space is required.
Example:

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 5
2. Input: [5, 4, 3, 2, 1] | Output: 5
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -1
4. Input: [100] | Output: 100
5. Input: [] | Output: -Infinity (Empty Array)

3. Divide and Conquer Approach (Recursive) (Optional - for people who understand recursion)

Idea: Recursively divide the array into two halves and find the maximum in each half. Compare the two maximums to get the overall maximum.
Steps:
1. Base case: If the array has one element, return that element.
2. Recursively find the maximum in the left half and the right half.
3. Return the greater of the two.
Time Complexity: O(n) - Every element is compared once.
Space Complexity: O(log n) - Due to recursive calls.
Example:

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 5
2. Input: [5, 4, 3, 2, 1] | Output: 5
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -1
4. Input: [100] | Output: 100
5. Input: [] | Output: undefined (Empty Array)

Note :-

All methods discussed have a time complexity of O(n), but the space complexity varies. The brute force and built-in methods are more straightforward and efficient in terms of space, while the recursive method uses more space due to the recursive stack.

Previous Next