I am trying to solve Sum of Subarray Ranges question on leetcode, it's giving me Time Limit Exceeded so I guess my code isn't optimized well and needs more efficient solutions. But I am not so good at it so to be specific how can I remove two for-loops with one in my code.
Ques1: Sum of Subarray Ranges
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:
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.
Ques link
My code: Test cases: 52/71
var subArrayRanges = function(nums) {
let maxSub=0;
for(let i=0; i<nums.length; i++){
let arr=[];
arr.push(nums[i])
for(let j=i+1; j<nums.length; j++){
arr.push(nums[j]);
maxSub=maxSub+(Math.max(...arr)) - (Math.min(...arr));
}
}
return maxSub
};
How can I optimize my code so that it can run all test cases?
A hint for the optimization part: when the j-loop gets a new element, only that element can affect the minimum/maximum of the given subarray. So you don't actually have to build the subarray and run actual min()/max() calls on it, only store its min and max values (which are the same [i] element at the beginning of the inner loop) and compare+update them using the incoming new element (the [j] one):
var subArrayRanges = function(nums) {
let maxSub=0;
for(let i=0; i<nums.length; i++){
let min=nums[i],max=nums[i];
for(let j=i+1; j<nums.length; j++){
if(nums[j]<min)min=nums[j];
if(nums[j]>max)max=nums[j];
maxSub=maxSub+max-min;
}
}
return maxSub
};