Sum of Subarray Ranges Leetcode Solution

Difficulty Level Medium
Frequently asked in AmazonViews 4397

Problem Statement

The Sum of Subarray Ranges Leetcode Solution – says that you’re given an integer array nums of max size 10^3. We need to return the sum of all subarray ranges of the given array.

The range of a subarray is defined as the difference between the largest and smallest element of the subarray.

Example:

Sum of Subarray Ranges Leetcode Solution

 

Input: nums = [1,2,3]
Output: 4

Explanation:

  • All subarrays are [1], [1,2], [1,2,3], [2], [2,3], [3].
  • Maximum and Minimum elements of all respective subarrays are [1,1], [1,2], [1,3], [2,2], [2,3], [3,3], where [min_element, max_element].
  • Differences between maximum and minimum element of the subarrays are:- [0], [1], [2], [0], [1], [0].
  • Sum of all above values :-  1+2+1 = 4
Input: [4,-2,-3,4,1]
Output: 59

Explanation:

Approach

Idea1:

  1. Note that the max size of the array is 10^3, hence we solve the problem in O(N^2) time.
  2. In the brute force approach, consider every subarray and find the maximum as well as the minimum element of the subarray, and sum up all the differences between the maximum and minimum value.

Idea2:

  1. The main idea to solve this problem in linear time is to use a Stack.
  2. Find next greater element and next smaller element indices to the left as well right of every array value.
  3. Now, for every array index i, this value remains maximum or minimum in the range [left[i]+1,right[i]+1], where left[i] = index of first smaller/greater element to the left of i, and right[i] = index of first smaller/greater element to the right of i.
  4. Increment the answer by element*length of range in case of maximum, while decrementing the answer by the length of element*length of range in case of minimum. Note that ranges will be different in the case of maximum and minimum.
  5. Check the linear time code at the end of this post.

Code

C++ Sum of Subarray Ranges O(N^2) Time Leetcode  Solution based on Idea 1:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0,n = nums.size();
        for(int i=0;i<n;i++){
            int mx = INT_MIN,mn = INT_MAX;
            for(int j=i;j<n;j++){
                mx = max(mx,nums[j]);
                mn = min(mn,nums[j]);
                
                ans += mx-mn;
            }
        }
        return ans;
    }
};

Java Sum of Subarray Ranges O(N^2) Time Leetcode Solution based on Idea 1:

class Solution {
    public long subArrayRanges(int[] nums) {
        long ans = 0;
        for(int i=0;i<nums.length;i++){
            int maxi = nums[i],mini = nums[i];
            for(int j=i+1;j<nums.length;j++){
                mini = Math.min(mini,nums[j]);
                maxi = Math.max(maxi,nums[j]);
                ans = ans + (maxi-mini);
            }
        }
        return ans;
    }
}

C++ Sum of Subarray Ranges O(N) Time Leetcode Solution based on Idea 2:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        vector<int> left_greater(n,-1),right_greater(n,n);
        vector<int> left_smaller(n,-1),right_smaller(n,n);
        stack<int> s1,s2,s3,s4;
        for(int i=0;i<n;i++){
            while(!s1.empty() and nums[s1.top()]<nums[i]){
                right_greater[s1.top()] = i;
                s1.pop();
            }
            s1.push(i);
        }        
        for(int i=n-1;i>=0;i--){
            while(!s2.empty() and nums[s2.top()]<=nums[i]){
                left_greater[s2.top()] = i;
                s2.pop();
            }
            s2.push(i);
        }        
        for(int i=0;i<n;i++){
            while(!s3.empty() and nums[s3.top()]>nums[i]){
                right_smaller[s3.top()] = i;
                s3.pop();
            }
            s3.push(i);
        }
        for(int i=n-1;i>=0;i--){
            while(!s4.empty() and nums[s4.top()]>=nums[i]){
                left_smaller[s4.top()] = i;
                s4.pop();
            }
            s4.push(i);
        }
        long long ans = 0;
        for(int i=0;i<n;i++){
            long long maxi = (right_greater[i] - i) * (i - left_greater[i]);
            long long mini = (right_smaller[i] - i) * (i - left_smaller[i]);
            ans += (maxi*nums[i]);
            ans -= (mini*nums[i]);
        }        
        return ans;
    }
};

Complexity Analysis for Sum of Subarray Ranges Leetcode Solution

Time Complexity

The time complexity of the code which is based on idea 1 is O(N^2) since we are considering every subarray which takes O(N^2) time.

Also, the time Complexity of the code based on idea 2 is O(N) since we use a stack to find the next greater/smaller element which takes O(N) linear time.

Space Complexity

The space complexity of the code based on idea 1 is O(1) since we’re working with variables at each time.

The space complexity of the code based on idea 2 is O(N) since we use a linear vector to store the indices of the next greater and smaller element of every index.

Translate »