Calculate Array Range — Problem Statement & Solution Guide
Problem Description
You are given a sequence of integers. Your task is to determine the range of the array, defined as the difference between the largest and the smallest element in the sequence. The input consists of two lines: the first line contains a single integer n (1 ≤ n ≤ 10^5) representing the number of elements, and the second line contains n space‑separated integers a_1, a_2, …, a_n (−10^9 ≤ a_i ≤ 10^9). The output should be a single integer: the value of max(a_i) − min(a_i). The solution must run in linear time and use constant additional space beyond the input array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Calculate Array Range"
WHY DOES IT MATTER?
Finding global extremes in a single pass is a classic reduction pattern that appears in many real‑world analytics tasks, from sensor data summarization to financial risk calculations. Mastering this pattern demonstrates an ability to turn O(n²) brute force into O(n) linear solutions, a core skill for performance‑critical software.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the range depends only on two values—global minimum and maximum—so you can discard all other information during the scan, eliminating the need for sorting or auxiliary data structures.
REAL-WORLD CONNECTION
Consider a distributed logging system that aggregates latency metrics from thousands of servers. Each server reports its min and max latency; a central collector then computes the overall range, mirroring the local‑global reduction used in this problem.
During an interview, read the input once, update two variables, and defer any arithmetic until after the loop. This avoids overflow and keeps the code clean; also, explicitly mention the O(1) extra space to signal awareness of memory constraints.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The range of an array is defined as max(array) − min(array). Computing it efficiently hinges on the ability to locate the global maximum and minimum in a single linear scan. A naive double‑loop that compares every pair of elements would require O(n²) time, which quickly becomes infeasible when n reaches 10⁵, the upper bound typical for competitive programming and interview problems. The optimal paradigm leverages the fact that the maximum and minimum are *associative* and *idempotent* operations; they can be updated incrementally as each element is read, guaranteeing a single‑pass solution.
In practice, we maintain two variables, currentMin and currentMax, initialized to the first element. As we iterate through the remaining n‑1 elements, we compare each value against these trackers, updating them when a new extreme is found. This approach runs in O(n) time and O(1) auxiliary space, satisfying both the time‑limit constraints and memory limits for large inputs. The simplicity of the algorithm also makes it robust against overflow concerns, as the subtraction is performed only once after the scan, using 64‑bit integers to accommodate the full input range (‑10⁹ ≤ aᵢ ≤ 10⁹).
Interview Questions on This Problem
Q1How would you modify the solution if you also needed to return the indices of the minimum and maximum elements?
Track the index alongside each extreme: when updating currentMin or currentMax, also store the current loop index. After the scan, return both values and their stored indices. This still runs in O(n) time and O(1) extra space.
Q2Can you compute the range of a stream of numbers where the total count is unknown beforehand?
Yes. Initialize min and max with the first streamed value, then for each subsequent value update them as before. Since the algorithm only needs the current extremes, it works for unbounded streams and uses constant memory.
Q3What would be the impact on time and space complexity if the array were stored in a distributed system across multiple nodes?
Each node can compute its local min and max in O(local_n) time and O(1) space. A final reduction step aggregates these local extremes to a global min and max in O(k) time, where k is the number of nodes, still O(n) overall time and O(k) additional space for the reduction results.
Examples
Input
5 1 3 5 7 9
Output
8
Explanation: The maximum value is 9 and the minimum is 1. Their difference is 9 − 1 = 8.
Input
4 -2 -5 0 3
Output
8
Explanation: Maximum is 3, minimum is -5. Difference: 3 − (-5) = 8.
Input
6 10 10 10 10 10 10
Output
0
Explanation: All elements are equal; max and min are both 10, so the range is 0.
Constraints
- 1 <= n <= 10^5
- -10^9 <= a_i <= 10^9
- The array may contain duplicate values
- The algorithm must run in O(n) time and O(1) extra space
Optimal Approach & Strategy
Perform a single linear scan, updating min and max on the fly, achieving O(n) time and O(1) extra space.
Brute Force Approach
Compare every pair of elements to find the global minimum and maximum, resulting in O(n²) time.
Verified Code Solutions
function solution(nums) {
let min = Math.min(...nums);
let max = Math.max(...nums);
return max - min;
}class Solution {
public:
int solution(vector<int>& nums) {
int min = INT_MIN;
int max = INT_MIN;
for (int num : nums) {
if (num < min) min = num;
if (num > max) max = num;
}
return max - min;
}
};class Solution {
public int solution(int[] nums) {
int min = Integer.MIN_VALUE;
int max = Integer.MIN_VALUE;
for (int num : nums) {
if (num < min) min = num;
if (num > max) max = num;
}
return max - min;
}
}def solution(nums):
return max(nums) - min(nums)function solution(nums) {
let min = Math.min(...nums);
let max = Math.max(...nums);
return max - min;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.