Sponsored
Sponsored
The brute force approach involves calculating the sum of all possible subarrays in the given array. Once all subarray sums are computed, we can sort this list of sums. Finally, sum the elements from the sorted list between the given 'left' and 'right' indices, returning the result modulo 10^9 + 7. This approach is straightforward to implement but not necessarily optimal in terms of time complexity.
Time Complexity: O(n^2 log n) due to calculating O(n^2) subarray sums and sorting them.
Space Complexity: O(n^2), for storing subarray sums.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int rangeSum(int* nums, int numsSize, int n, int left, int right) {
9 int mod = 1000000007;
10 int totalSubarrays = n * (n + 1) / 2;
11 int* subarraySums = (int*)malloc(totalSubarrays * sizeof(int));
12 int index = 0;
13
14 for (int i = 0; i < numsSize; i++) {
15 int sum = 0;
16 for (int j = i; j < numsSize; j++) {
17 sum += nums[j];
18 subarraySums[index++] = sum;
19 }
20 }
21
22 qsort(subarraySums, totalSubarrays, sizeof(int), compare);
23
24 int result = 0;
25 for (int i = left - 1; i < right; i++) {
26 result = (result + subarraySums[i]) % mod;
27 }
28
29 free(subarraySums);
30 return result;
31}
32
33int main() {
34 int nums[] = {1, 2, 3, 4};
35 int result = rangeSum(nums, 4, 4, 1, 5);
36 printf("%d\n", result);
37 return 0;
38}This implementation computes all possible subarray sums and stores them in an array subarraySums. Then, it sorts this array using C's built-in qsort function. Finally, it calculates the sum of elements from index left - 1 to right - 1 in this sorted array and returns the sum modulo 10^9 + 7.
This approach leverages a min-heap (priority queue) data structure to efficiently find the range of the smallest elements. By pushing subarray sums into the min-heap and ensuring its size does not exceed 'right', we can directly extract the required sum by polling from the min-heap. This method avoids complete sorting and is more efficient than direct sorting for larger input sizes.
Time Complexity: O(n^2 log M), where M is the maximum heap size (i.e., 'right').
Space Complexity: O(M), since we maintain only 'M' elements in the heap.
using System.Collections.Generic;
public class Solution {
public int RangeSum(int[] nums, int n, int left, int right) {
int MOD = 1000000007;
PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
minHeap.Enqueue(sum, sum);
}
}
int result = 0;
for (int k = 1; k <= right; k++) {
int currentSum = minHeap.Dequeue();
if (k >= left) {
result = (result + currentSum) % MOD;
}
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3, 4};
Console.WriteLine(sol.RangeSum(nums, 4, 1, 5));
}
}This C# implementation exploits the PriorityQueue to skillfully manage subarray sums, retaining direct control over sum calculations. The heap approach furnishes optimized performance by tackling only pertinent sums within heap operations, presenting a streamlined model for problem solving.