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] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
The Brute Force Approach involves iterating over all possible subarrays of the given array. For each subarray, find the maximum and minimum elements, and calculate the difference. Sum all these differences to get the final answer. While this approach is simple, it is not efficient for larger arrays due to its quadratic time complexity.
This approach iterates over the array, using two nested loops where the outer loop sets the starting point of the subarray and the inner loop extends the subarray to all subsequent points. It calculates both the maximum and minimum for each subarray, computing their difference, which is accumulated into the total sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the length of the array, due to the nested loop structure.
Space Complexity: O(1), no extra data structures are used apart from loop variables.
The Monotonic Stack Approach optimizes the calculation by focusing on the contribution of each element as a maximum or minimum in various subarrays. By using two stacks, the solution efficiently determines the range extend of each number within the subarray, deriving the number of subarrays it could be the maximum or minimum of. This optimized approach emphasizes reducing redundant calculations commonly inherent in brute force methods.
This C solution centers upon leveraging two stacks for determining the role of each element both as a minimum and maximum across potential subarrays, to accumulate the distinct contribution of each element to the total subarray range.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), regarded as linear due to the stack operations limiting the number of necessary operations to a reduced count.
Space Complexity: O(n), for storing the elements in the stack structures.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array, due to the nested loop structure. |
| Monotonic Stack Approach | Time Complexity: O(n), regarded as linear due to the stack operations limiting the number of necessary operations to a reduced count. |
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python • NeetCode • 266,724 views views
Watch 9 more video solutions →Practice Sum of Subarray Ranges with our built-in code editor and test cases.
Practice on FleetCode