Sum of subarray ranges

Array Stack Monotonic Stack

60.8% acceptance

Feb 25, 2026

2975

143

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut sum = 0i64;
    for i in 0..n {
      let (mut mn, mut mx) = (nums[i], nums[i]);
      for j in i..n {
        mn = mn.min(nums[j]);
        mx = mx.max(nums[j]);
        sum += (mx - mn) as i64;
      }
    }
    sum
  }
}