Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find Maximum in Array

EASYProblemSolveExternal Links

Description

Given a list of N integers representing the heights of mountains, find and return the height of the tallest mountain.

In other words, you are given an array of N positive integers. Your task is to determine the maximum (largest) value present in the array and output it.

Examples

Example 1

Input: arr = [4, 7, 6, 3, 1]

Output: 7

Explanation: We compare every element in the array: 4, 7, 6, 3, and 1. The value 7 at index 1 is greater than all other elements. Therefore, the height of the tallest mountain is 7.

Example 2

Input: arr = [10, 20, 5, 15]

Output: 20

Explanation: Among all elements — 10, 20, 5, and 15 — the value 20 at index 1 is the largest. No other element exceeds 20, so we return 20.

Example 3

Input: arr = [42]

Output: 42

Explanation: When the array contains only one element, that element is trivially the largest. We return 42.

Constraints

  • 1 ≤ N ≤ 100000
  • 0 ≤ arr[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to find the largest element is to first sort the entire array in ascending order. Once sorted, the maximum element will always be at the very last position of the array. We simply return that last element.

Think of it like arranging a row of books by height from shortest to tallest on a shelf. After you finish arranging them, the tallest book will be at the far right end — you just pick it up without comparing anything further.

Step-by-Step Explanation

Let's trace through with arr = [4, 7, 6, 3, 1]:

Step 1: We receive the unsorted array: [4, 7, 6, 3, 1].

Step 2: Sort the array in ascending order. After sorting: [1, 3, 4, 6, 7].

Step 3: The last element of the sorted array is 7.

Step 4: Return 7 as the maximum value.

The sorting does all the heavy lifting here. We do not need to manually compare elements — the sort guarantees the largest value lands at the end.

Algorithm

  1. Take the input array of N integers.
  2. Sort the array in ascending (non-decreasing) order.
  3. Return the element at the last index (index N-1).

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaximum(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        return arr[arr.size() - 1];
    }
};
class Solution:
    def findMaximum(self, arr: list[int]) -> int:
        arr.sort()
        return arr[-1]
import java.util.Arrays;

class Solution {
    public int findMaximum(int[] arr) {
        Arrays.sort(arr);
        return arr[arr.length - 1];
    }
}

Complexity Analysis

Time Complexity: O(N log N)

Sorting the array dominates the cost. Standard comparison-based sorts like merge sort or Timsort run in O(N log N) time. Reading the last element afterward is O(1), so the total time is O(N log N).

Space Complexity: O(1) to O(N)

Depending on the sorting algorithm used, extra space may be required. In-place sorts like quicksort use O(log N) stack space, while merge sort uses O(N). For the purpose of this analysis, sorting may require up to O(N) auxiliary space.

Why This Approach Is Not Efficient

Sorting the entire array just to find a single value — the maximum — is wasteful. Sorting rearranges every element into order, performing O(N log N) comparisons, when all we need is the answer to one question: "Which element is the largest?"

With N up to 100,000, the sorting approach performs roughly 100,000 × 17 ≈ 1,700,000 operations. While this is fast enough to pass time limits, it is fundamentally doing far more work than necessary.

The key insight is: we do not need the elements in any particular order. We only need to visit each element once and remember the largest value we have encountered. This observation leads us to a simpler and faster O(N) solution — a single linear scan.

Optimal Approach - Linear Scan

Intuition

Imagine you are walking along a row of mountains and you want to remember the tallest one. You do not need to rearrange the mountains — you just need a good memory. Start by looking at the first mountain and noting its height. Then, as you walk past each subsequent mountain, compare its height to the tallest one you have seen so far. If the current mountain is taller, update your record. By the time you reach the end of the row, the height stored in your memory is the answer.

This is exactly what a linear scan does: traverse the array once from left to right, maintaining a running maximum that gets updated whenever a larger value is found.

Step-by-Step Explanation

Let's trace through with arr = [4, 7, 6, 3, 1]:

Step 1: Initialize max_val with the first element.

  • max_val = arr[0] = 4

Step 2: Move to index 1: arr[1] = 7.

  • Is 7 > 4? Yes.
  • Update max_val = 7.

Step 3: Move to index 2: arr[2] = 6.

  • Is 6 > 7? No.
  • max_val remains 7.

Step 4: Move to index 3: arr[3] = 3.

  • Is 3 > 7? No.
  • max_val remains 7.

Step 5: Move to index 4: arr[4] = 1.

  • Is 1 > 7? No.
  • max_val remains 7.

Step 6: We have visited every element. Return max_val = 7.

Finding the Maximum — Linear Scan — Watch how we maintain a running maximum while scanning left to right. The max_val only updates when we encounter a value larger than the current best.

Algorithm

  1. Initialize a variable max_val with the value of the first element of the array.
  2. Iterate through the array starting from the second element (index 1) to the last element:
    • If the current element is greater than max_val, update max_val to the current element.
  3. After the loop completes, return max_val.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int findMaximum(vector<int>& arr) {
        int maxVal = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        return maxVal;
    }
};
class Solution:
    def findMaximum(self, arr: list[int]) -> int:
        max_val = arr[0]
        for i in range(1, len(arr)):
            if arr[i] > max_val:
                max_val = arr[i]
        return max_val
class Solution {
    public int findMaximum(int[] arr) {
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
        return maxVal;
    }
}

Complexity Analysis

Time Complexity: O(N)

We traverse the array exactly once, visiting each of the N elements one time. At each element we perform a single comparison, which is an O(1) operation. The total number of comparisons is N-1, giving us O(N) overall.

This is provably optimal — any algorithm that finds the maximum must inspect every element at least once, because an unexamined element could be the largest. Therefore, O(N) is a tight lower bound.

Space Complexity: O(1)

We use only a single extra variable (max_val) to track the running maximum. This does not grow with input size, so the space usage is constant.