DSA-Java-Leetcode/1508. Range Sum of Sorted Subarray Sums at main · risitadas/DSA-Java-Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution
{
    int MOD = (int)1e9+7;

    public int rangeSum(int[] nums, int n, int left, int right)
    {
        int[] arr= new int[n*(n+1)/2];

        for(int i=0,k=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
               sum+=nums[j];
               arr[k++]=sum;
            }
        }

        Arrays.sort(arr);
        int sum=0;
        for(int i=left;i<=right;i++)
        {

            sum=(sum+arr[i-1]) % MOD;
        }

        return sum;
    }


/*

Runtime 170 ms, Memory 72.43 MB


    static int MOD = 1000000007;

    public int rangeSum(int[] nums, int n, int left, int right)
    {

        ArrayList<Integer> subArrSum = new ArrayList<>();
        long rangeSum = 0;

        for(int i=0; i<n; i++)
        {
            int sum=0;

            for(int j=i; j<n; j++)
            {
                sum += nums[j];
                subArrSum.add(sum);

            }
        }

        Collections.sort(subArrSum);

        for(int i=left-1; i< right; i++)
        {
            rangeSum = (rangeSum + subArrSum.get(i)) % MOD;

        }

        return (int)rangeSum;

    }


    */
}