3. Find the Maximum and Minimum Element in an Array

Given an array of n integers, print the maximum element followed by the minimum element, separated by a space.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print the maximum element followed by the minimum element, separated by a space.

1 <= n <= 10^5

Initializing both max and min to the FIRST element (not to 0 or some arbitrary sentinel) correctly handles arrays containing all-negative or all-positive numbers without any special-casing.

Look through a list of numbers and find both the biggest and the smallest one. Brute force: Sort the array and take the first and last elements - correct, but sorting costs O(n log n) when a single linear scan can do the same job in O(n). Optimised: Tracking a running max and running min together in ONE pass avoids the unnecessary cost of sorting entirely - you only ever need to compare each element once against your two running trackers.

Process the array two elements at a time: first compare the pair against each other to determine which is locally larger and which is locally smaller (1 comparison), then only compare the locally-larger one against the running maximum and the locally-smaller one against the running minimum (2 more comparisons), for 3 comparisons per pair of elements instead of 4 in the straightforward linear scan. This reduces the total number of comparisons from roughly 2n down to about 3n/2, which is the theoretical minimum number of comparisons needed to find both the max and min, while keeping the same linear time and constant space. Time: O(n) Space: O(1)

For each element in the array, compare it against every other element to determine whether it is greater than all of them (making it the maximum) or smaller than all of them (making it the minimum). This correctly identifies the max and min by definition, but comparing every element against every other element is far more comparisons than needed for a task this simple. Time: O(n^2) Space: O(1)

Initialize both a running maximum and running minimum to the first element, then scan through the rest of the array once, updating the running max whenever a larger value is seen and the running min whenever a smaller value is seen. This is a large improvement over the nested-loop approach because each element is only compared a constant number of times (against the current max and current min) rather than against every other element. Time: O(n) Space: O(1)

1. Start by assuming the first element is both the current max and current min. 2. Walk through the rest of the array one element at a time. 3. Whenever you see something bigger than your current max, update the max; whenever you see something smaller than your current min, update the min. 4. After the single pass, you have both answers.

Time: O(n) - one single pass through the array. Space: O(1) - just two tracking variables, regardless of array size.

n = 1 (max and min are the same element); duplicate values including a repeated max or min, as in the example; and n = 10^5 (largest, confirming a single linear scan suffices).

This trivial-sounding problem is often used as a quick warm-up question specifically to check you don't reach for an unnecessary sort - a strong first answer shows efficiency-awareness from the very first question.