Difference of Segment Extremes — Problem Statement & Solution Guide
Problem Description
Given an integer array nums of even length n, calculate the difference between the maximum value in the first half of the array and the minimum value in the second half of the array.
Examples
Input
[1, 2, 3, 4]
Output
-1
Explanation: Step-by-step: Given the input [1, 2, 3, 4], we first split the array into two halves: [1, 2] and [3, 4]. The maximum value in the first half is 2 and the minimum value in the second half is 3. Therefore, the difference is 2 - 3 = -1.
Input
[-5, 1, -3, 2]
Output
4
Explanation: Step-by-step: Given the input [-5, 1, -3, 2], we first split the array into two halves: [-5, 1] and [-3, 2]. The maximum value in the first half is 1 and the minimum value in the second half is -3. Therefore, the difference is 1 - (-3) = 4.
Constraints
- 2 <= nums.length <= 10^5
- nums.length is even
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
The optimized approach uses a single-pass linear scan. By iterating through the first half of the array, we can track the maximum element. Similarly, by iterating through the second half, we can track the minimum element. This results in an optimal O(N) time complexity and O(1) auxiliary space.
Brute Force Approach
A brute-force approach would involve sorting the first half of the array in ascending order to find the maximum element (at the end of the first half), and sorting the second half of the array to find the minimum element (at the start of the second half). This takes O(N log N) time due to the sorting operations and consumes extra space for storing the copies of the subarrays.
Verified Code Solutions
function differenceOfSegmentExtremes(nums) {
const n = nums.length;
if (n < 2) return 0;
const mid = Math.floor(n / 2);
let maxFirst = -Infinity;
let minSecond = Infinity;
for (let i = 0; i < mid; i++) {
maxFirst = Math.max(maxFirst, nums[i]);
}
for (let i = mid; i < n; i++) {
minSecond = Math.min(minSecond, nums[i]);
}
return maxFirst - minSecond;
}#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
class Solution {
public:
int differenceOfSegmentExtremes(std::vector<int>& nums) {
int n = nums.size();
int mid = n / 2;
long long maxFirst = LLONG_MIN;
for (int i = 0; i < mid; ++i) {
if (nums[i] > maxFirst) maxFirst = nums[i];
}
long long minSecond = LLONG_MAX;
for (int i = mid; i < n; ++i) {
if (nums[i] < minSecond) minSecond = nums[i];
}
return (int)(maxFirst - minSecond);
}
};class Solution {
public int solution(int[] nums) {
if (nums.length < 2) {
return 0;
}
int mid = nums.length / 2;
int max_first_half = Integer.MIN_VALUE;
int min_second_half = Integer.MAX_VALUE;
for (int i = 0; i < mid; i++) {
max_first_half = Math.max(max_first_half, nums[i]);
}
for (int i = mid; i < nums.length; i++) {
min_second_half = Math.min(min_second_half, nums[i]);
}
return max_first_half - min_second_half;
}
}def solution(nums):
if len(nums) < 2:
return 0
mid = len(nums) // 2
max_first_half = max(nums[:mid])
min_second_half = min(nums[mid:])
return max_first_half - min_second_halffunction differenceOfSegmentExtremes(nums) {
const n = nums.length;
if (n < 2) return 0;
const mid = Math.floor(n / 2);
let maxFirst = -Infinity;
let minSecond = Infinity;
for (let i = 0; i < mid; i++) {
maxFirst = Math.max(maxFirst, nums[i]);
}
for (let i = mid; i < n; i++) {
minSecond = Math.min(minSecond, nums[i]);
}
return maxFirst - minSecond;
}Asked in Top Tech Interviews
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.