• + 0 comments

    Used the idea o modifiers, but without the n-sized array. Also in C#. Complexity is O(m log m), that can be less than O(n).

    static long arrayManipulation(int n, int m, int[][] queries) {
        long max = 0;
    
        SortedDictionary<int,long> fakeArray = new SortedDictionary<int,long>();
    
        // 'm' times
                for (int i=0; i<m; i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            int k = queries[i][2];
    
            // bit optimization: a '0' valued query will make no difference on resultant ones
            if (queries[i][2] <= 0) continue;
    
            if (!fakeArray.ContainsKey(a)) {  // O( log m )
                fakeArray.Add(a, k);                 // O( log m )
            }
            else {
                fakeArray[a] += k;                    // O( log m )
            }
    
            if (b < n) {
                b++;
                if (!fakeArray.ContainsKey(b)) {   // O( log m )
                    fakeArray.Add(b, -1 * k);          // O( log m )
                }
                else {
                    fakeArray[b] -= k;                      // O( log m )
                }
            }
        }
    
        long current = 0;
        foreach(long modifier in fakeArray.Values){ // O( 2*m )
            current += modifier;
            if (current > max) max = current;
        }
    
        return max;
    }