easyArraysPattern: Basic Traversal
Difference of Segment Extremes Solution
Problem Statement
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. Specifically, find the maximum value in the subarray `nums[0 ... n/2 - 1]` and the minimum value in the subarray `nums[n/2 ... n - 1]`, and return the result of subtracting the minimum of the second half from the maximum of the first half. Follow-up: How would you modify your solution if the array length could be odd, with the middle element included in both halves?
Examples
Example 1:
Input:nums = [3, 8, 2, 5, 1, 6]
Output:7
Explanation: The first half is [3, 8, 2] with a maximum of 8. The second half is [5, 1, 6] with a minimum of 1. The difference is 8 - 1 = 7.
Example 2:
Input:nums = [-10, -5, -20, -1]
Output:15
Explanation: The maximum of the first half [-10, -5] is -5. The minimum of the second half [-20, -1] is -20. The difference is -5 - (-20) = 15.
Constraints
- 2 <= nums.length <= 10^5
- nums.length is even
- -10^9 <= nums[i] <= 10^9
Time: O(N) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
class Solution:
def difference_of_segment_extremes(self, nums: List[int]) -> int:
n = len(nums)
mid = n // 2
# First half: indices 0 to mid-1
max_first = max(nums[:mid])
# Second half: indices mid to n-1
min_second = min(nums[mid:])
return int(max_first - min_second)
def difference_of_segment_extremes_odd(self, nums: List[int]) -> int:
# Follow-up: If odd, middle element is included in both halves
# Indices: [0 ... mid] and [mid ... n-1]
n = len(nums)
mid = n // 2
max_first = max(nums[:mid + 1])
min_second = min(nums[mid:])
return int(max_first - min_second)