Find the Minimum and Maximum with Constant Space
Solve this ProblemEasy10 min
Topics
BasicsComplexityArrays
Companies
TCSInfosysWipro
Given an array
nums, return [minimum, maximum].
Besides time, algorithms use memory. Space complexitySpace ComplexityHow much extra memory an algorithm needs, as a function of the input size n — not counting the input itself. measures the extra memory an algorithm needs beyond its input. Sorting a copy needs a second array as big as the first (O(n) space); a single pass that remembers only the smallest and largest values so far needs two variables, whatever the input size — constant spaceConstant Space O(1)Extra memory that stays the same no matter how large the input is..
Test Case 1:
Input:nums = [7, -2, 9, 4]
Output:[-2, 9]
Explanation:Smallest −2, largest 9.
Test Case 2:
Input:nums = [5]
Output:[5, 5]
Explanation:A single value is both the minimum and the maximum.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Sort a CopyGood
Copy the array, sort the copy, and read the first and last elements. It is short and correct, but the copy needs as much extra memory as the input itself — O(n) extra space — and sorting does far more work than finding two values requires.
Time
O(n log n)Space
O(n)Java
class Solution {
public int[] minAndMax(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
return new int[] {sorted[0], sorted[sorted.length - 1]};
}
}One Pass with Two VariablesOptimal
Keep just two variables, low and high, both starting at the first element. Walk the array once; whenever a value is smaller than low or larger than high, update that variable. Two variables are needed no matter how long the array is, so the extra space is O(1).
Time
O(n)Space
O(1)Java
class Solution {
public int[] minAndMax(int[] nums) {
int low = nums[0];
int high = nums[0];
for (int value : nums) {
if (value < low) {
low = value;
}
if (value > high) {
high = value;
}
}
return new int[] {low, high};
}
}