Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.
Example 2:
Input: nums = [1,3,3] Output: 4 Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [3], range = 3 - 3 = 0 [3], range = 3 - 3 = 0 [1,3], range = 3 - 1 = 2 [3,3], range = 3 - 3 = 0 [1,3,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.
Example 3:
Input: nums = [4,-2,-3,4,1] Output: 59 Explanation: The sum of all subarray ranges of nums is 59.
Constraints:
1 <= nums.length <= 1000-109 <= nums[i] <= 109Follow-up: Could you find a solution with O(n) time complexity?
Problem summary: You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray. Return the sum of all subarray ranges of nums. A subarray is a contiguous non-empty sequence of elements within an array.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Stack
[1,2,3]
[1,3,3]
[4,-2,-3,4,1]
next-greater-element-i)sum-of-subarray-minimums)number-of-visible-people-in-a-queue)count-number-of-homogenous-substrings)sum-of-total-strength-of-wizards)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2104: Sum of Subarray Ranges
class Solution {
public long subArrayRanges(int[] nums) {
long ans = 0;
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
int mi = nums[i], mx = nums[i];
for (int j = i + 1; j < n; ++j) {
mi = Math.min(mi, nums[j]);
mx = Math.max(mx, nums[j]);
ans += (mx - mi);
}
}
return ans;
}
}
// Accepted solution for LeetCode #2104: Sum of Subarray Ranges
func subArrayRanges(nums []int) int64 {
var ans int64
n := len(nums)
for i := 0; i < n-1; i++ {
mi, mx := nums[i], nums[i]
for j := i + 1; j < n; j++ {
mi = min(mi, nums[j])
mx = max(mx, nums[j])
ans += (int64)(mx - mi)
}
}
return ans
}
# Accepted solution for LeetCode #2104: Sum of Subarray Ranges
class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for i in range(n - 1):
mi = mx = nums[i]
for j in range(i + 1, n):
mi = min(mi, nums[j])
mx = max(mx, nums[j])
ans += mx - mi
return ans
// Accepted solution for LeetCode #2104: Sum of Subarray Ranges
impl Solution {
pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut res: i64 = 0;
for i in 1..n {
let mut min = nums[i - 1];
let mut max = nums[i - 1];
for j in i..n {
min = min.min(nums[j]);
max = max.max(nums[j]);
res += (max - min) as i64;
}
}
res
}
}
// Accepted solution for LeetCode #2104: Sum of Subarray Ranges
function subArrayRanges(nums: number[]): number {
const n = nums.length;
let res = 0;
for (let i = 0; i < n - 1; i++) {
let min = nums[i];
let max = nums[i];
for (let j = i + 1; j < n; j++) {
min = Math.min(min, nums[j]);
max = Math.max(max, nums[j]);
res += max - min;
}
}
return res;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.