Find the Maximum Element in an Array

Find and return the largest element in an array of integers

Language Selection

Choose your preferred programming language

Showing: Python

Find the Maximum Element in an Array

Problem Statement

Given an array of integers, find and return the maximum (largest) element in the array.

Input/Output Specifications

Input: An array of integers nums where 1 <= nums.length <= 10^5 and -10^9 <= nums[i] <= 10^9
Output: An integer representing the maximum element in the array

Constraints

The array contains at least one element
Array elements can be negative, positive, or zero
Array is not guaranteed to be sorted

Examples

Example 1:

Input: nums = [3, 1, 4, 1, 5, 9, 2, 6]
Output: 9
Explanation: The largest element in the array is 9.

Example 2:

Input: nums = [-5, -2, -8, -1]
Output: -1
Explanation: Among all negative numbers, -1 is the largest.

Example 3:

Input: nums = [42]
Output: 42
Explanation: Single element array returns that element.

Solution Approaches

Approach 1: Linear Scan (Optimal)

Algorithm Explanation:

Initialize a variable to track the maximum element, starting with the first element
Iterate through the array starting from the second element
For each element, compare it with the current maximum
If the current element is greater, update the maximum
Return the maximum after scanning all elements

Implementation:

Python:

def find_maximum(nums):
    """
    Find maximum element using linear scan
    Time: O(n)
    Space: O(1)
    """
    if not nums:
        raise ValueError("Array cannot be empty")
    
    max_element = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > max_element:
            max_element = nums[i]
    
    return max_element

# Alternative using built-in max function
def find_maximum_builtin(nums):
    """
    Find maximum element using built-in max function
    Time: O(n)
    Space: O(1)
    """
    if not nums:
        raise ValueError("Array cannot be empty")
    
    return max(nums)

Java:

class Solution {
    /**
     * Find maximum element using linear scan
     * Time: O(n)
     * Space: O(1)
     */
    public int findMaximum(int[] nums) {
        if (nums.length == 0) {
            throw new IllegalArgumentException("Array cannot be empty");
        }
        
        int maxElement = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxElement) {
                maxElement = nums[i];
            }
        }
        
        return maxElement;
    }
    
    // Alternative using Java 8 Streams
    public int findMaximumStream(int[] nums) {
        if (nums.length == 0) {
            throw new IllegalArgumentException("Array cannot be empty");
        }
        
        return Arrays.stream(nums).max().orElseThrow();
    }
}

Go:

// findMaximum - Find maximum element using linear scan
// Time: O(n)
// Space: O(1)
func findMaximum(nums []int) int {
    if len(nums) == 0 {
        panic("Array cannot be empty")
    }
    
    maxElement := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > maxElement {
            maxElement = nums[i]
        }
    }
    
    return maxElement
}

// Alternative using range loop
func findMaximumRange(nums []int) int {
    if len(nums) == 0 {
        panic("Array cannot be empty")
    }
    
    maxVal := nums[0]
    for _, val := range nums[1:] {
        if val > maxVal {
            maxVal = val
        }
    }
    
    return maxVal
}

JavaScript:

/**
 * Find maximum element using linear scan
 * Time: O(n)
 * Space: O(1)
 */
function findMaximum(nums) {
    if (!nums || nums.length === 0) {
        throw new Error("Array cannot be empty");
    }
    
    let maxElement = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > maxElement) {
            maxElement = nums[i];
        }
    }
    
    return maxElement;
}

// Alternative using Math.max with spread operator
function findMaximumBuiltin(nums) {
    if (!nums || nums.length === 0) {
        throw new Error("Array cannot be empty");
    }
    
    return Math.max(...nums);
}

// Alternative using reduce
function findMaximumReduce(nums) {
    if (!nums || nums.length === 0) {
        throw new Error("Array cannot be empty");
    }
    
    return nums.reduce((max, current) => Math.max(max, current));
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum element using linear scan
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int FindMaximum(int[] nums) {
        if (nums == null || nums.Length == 0) {
            throw new ArgumentException("Array cannot be empty");
        }
        
        int maxElement = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > maxElement) {
                maxElement = nums[i];
            }
        }
        
        return maxElement;
    }
    
    // Alternative using LINQ
    public int FindMaximumLinq(int[] nums) {
        if (nums == null || nums.Length == 0) {
            throw new ArgumentException("Array cannot be empty");
        }
        
        return nums.Max();
    }
}

Complexity Analysis:

Time Complexity: O(n) - We need to examine each element once
Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

Simple and intuitive approach
Optimal time complexity for unsorted arrays
Minimal space usage
Works with any comparable data type

Approach 2: Divide and Conquer

Algorithm Explanation:

Divide the array into two halves
Recursively find the maximum in each half
Return the maximum of the two maximums

Implementation:

Python:

def find_maximum_divide_conquer(nums):
    """
    Find maximum element using divide and conquer
    Time: O(n)
    Space: O(log n) due to recursion stack
    """
    if not nums:
        raise ValueError("Array cannot be empty")
    
    def find_max_helper(left, right):
        if left == right:
            return nums[left]
        
        mid = (left + right) // 2
        left_max = find_max_helper(left, mid)
        right_max = find_max_helper(mid + 1, right)
        
        return max(left_max, right_max)
    
    return find_max_helper(0, len(nums) - 1)

Java:

class Solution {
    /**
     * Find maximum element using divide and conquer
     * Time: O(n)
     * Space: O(log n) due to recursion stack
     */
    public int findMaximumDivideConquer(int[] nums) {
        if (nums.length == 0) {
            throw new IllegalArgumentException("Array cannot be empty");
        }
        
        return findMaxHelper(nums, 0, nums.length - 1);
    }
    
    private int findMaxHelper(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        int leftMax = findMaxHelper(nums, left, mid);
        int rightMax = findMaxHelper(nums, mid + 1, right);
        
        return Math.max(leftMax, rightMax);
    }
}

Go:

// findMaximumDivideConquer - Find maximum using divide and conquer
// Time: O(n)
// Space: O(log n) due to recursion stack
func findMaximumDivideConquer(nums []int) int {
    if len(nums) == 0 {
        panic("Array cannot be empty")
    }
    
    return findMaxHelper(nums, 0, len(nums)-1)
}

func findMaxHelper(nums []int, left, right int) int {
    if left == right {
        return nums[left]
    }
    
    mid := left + (right-left)/2
    leftMax := findMaxHelper(nums, left, mid)
    rightMax := findMaxHelper(nums, mid+1, right)
    
    if leftMax > rightMax {
        return leftMax
    }
    return rightMax
}

JavaScript:

/**
 * Find maximum element using divide and conquer
 * Time: O(n)
 * Space: O(log n) due to recursion stack
 */
function findMaximumDivideConquer(nums) {
    if (!nums || nums.length === 0) {
        throw new Error("Array cannot be empty");
    }
    
    function findMaxHelper(left, right) {
        if (left === right) {
            return nums[left];
        }
        
        const mid = Math.floor((left + right) / 2);
        const leftMax = findMaxHelper(left, mid);
        const rightMax = findMaxHelper(mid + 1, right);
        
        return Math.max(leftMax, rightMax);
    }
    
    return findMaxHelper(0, nums.length - 1);
}

C#:

public class Solution {
    /// <summary>
    /// Find maximum element using divide and conquer
    /// Time: O(n)
    /// Space: O(log n) due to recursion stack
    /// </summary>
    public int FindMaximumDivideConquer(int[] nums) {
        if (nums == null || nums.Length == 0) {
            throw new ArgumentException("Array cannot be empty");
        }
        
        return FindMaxHelper(nums, 0, nums.Length - 1);
    }
    
    private int FindMaxHelper(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        int leftMax = FindMaxHelper(nums, left, mid);
        int rightMax = FindMaxHelper(nums, mid + 1, right);
        
        return Math.Max(leftMax, rightMax);
    }
}

Complexity Analysis:

Time Complexity: O(n) - Still visits each element once
Space Complexity: O(log n) - Due to recursion stack depth

Trade-offs:

More complex implementation
Higher space complexity due to recursion
Can be useful for parallel processing scenarios
Good for understanding divide and conquer paradigm

Key Insights

Pattern Recognition: This is a fundamental linear search problem
Optimization: For unsorted arrays, linear scan is optimal - no algorithm can do better than O(n)
Built-in Functions: Most languages provide built-in max functions that are optimized
Initialization: Always initialize with the first element, not with a hardcoded value like 0 or Integer.MIN_VALUE

Edge Cases

Single Element Array: [5] → Returns 5
All Negative Numbers: [-1, -5, -3] → Returns -1
All Same Elements: [7, 7, 7] → Returns 7
Large Numbers: Arrays with values near integer limits
Minimum Array Size: Array with exactly one element

How Solutions Handle Edge Cases:

Single element: Base case returns that element
All negative: Comparison logic works correctly with negative numbers
All same: Algorithm correctly identifies any of the equal maximum values
Large numbers: Integer comparison handles full integer range
Empty array: Explicit validation with appropriate error handling

Test Cases

def test_find_maximum():
    # Basic case
    assert find_maximum([3, 1, 4, 1, 5, 9, 2, 6]) == 9
    
    # All negative
    assert find_maximum([-5, -2, -8, -1]) == -1
    
    # Single element
    assert find_maximum([42]) == 42
    
    # All same elements
    assert find_maximum([5, 5, 5, 5]) == 5
    
    # Maximum at beginning
    assert find_maximum([10, 2, 3, 1]) == 10
    
    # Maximum at end
    assert find_maximum([1, 2, 3, 10]) == 10
    
    # Large array
    large_array = list(range(1000))
    assert find_maximum(large_array) == 999
    
    print("All tests passed!")

test_find_maximum()

Follow-up Questions

Find Second Maximum: How would you modify the algorithm to find the second largest element?
Find Both Min and Max: Can you find both minimum and maximum in a single pass?
K Largest Elements: How would you find the k largest elements efficiently?
Maximum in Rotated Array: What if the array was sorted but rotated?
Streaming Maximum: How would you handle finding maximum in a stream of data?

Common Mistakes

Wrong Initialization: Initializing max with 0 instead of first element
- Problem: Fails when all elements are negative
- Solution: Always initialize with nums[0]
Off-by-one Errors: Starting loop from index 0 instead of 1
- Problem: Unnecessary comparison with itself
- Solution: Start loop from index 1
Empty Array Handling: Not checking for empty input
- Problem: Runtime errors or undefined behavior
- Solution: Add explicit validation
Integer Overflow: Not considering overflow in extreme cases
- Problem: Incorrect results with very large numbers
- Solution: Use appropriate data types for the language

Interview Tips

Start Simple: Begin with the linear scan approach - it’s optimal and easy to implement
Discuss Trade-offs: Mention that for unsorted arrays, O(n) is optimal
Handle Edge Cases: Always discuss and implement empty array validation
Alternative Approaches: Mention built-in functions but implement the manual approach
Follow-up Preparation: Be ready to extend to related problems like finding k-th largest

Concept Explanations

Linear Search Pattern: This problem demonstrates the fundamental linear search pattern where we examine each element exactly once. This pattern appears in many array problems and forms the basis for more complex algorithms.

Comparison-based Algorithms: Finding the maximum requires comparing elements, and the lower bound for comparison-based maximum finding is Ω(n-1) comparisons, making our O(n) solution optimal.

When to Apply: Use this pattern when you need to find a specific property (maximum, minimum, sum, etc.) that requires examining all elements in an unsorted collection.