2 Accepted Java Solution


  • 0
    A

    My first thought is that this is much like the skyline problem, so i came up with the solution I, which sorts boundaries of each update, so that we can calculate the total increase at each sub-interval and apply to result array. This should take O(max(length, update)*log(update)).

    I then find a much better solution from comments, which only takes O(max(length, update)).

    Both solutions are accepted.

    Solution I: Accepted, 24ms

    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        if (length == 0 || updates.length == 0)
            return result;
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] a1, int[] a2) {
                return a1[0] - a2[0]; // sort by index
            }
        });
        for (int[] update : updates) {
            int start = update[0], end = update[1], incr = update[2];
            q.add(new int[]{start, incr, 0}); // incr rises from index 'start'
            q.add(new int[]{end+1, incr, 1}); // NOTE: incr drops from index AFTER 'end'
        }
        q.add(new int[]{length, 0, 0}); // padding to the end; because update is triggered 
                                       // after encountering a new entry at this index.
        int prevIdx = 0, totalIncr = 0;
        while (!q.isEmpty()) {
            int idx = q.peek()[0];
            // trigger applying total incr for previous sub interval
            for (int i = prevIdx; i < idx; result[i++] = totalIncr);
            // find all bounaries falling at idx; could be more than 1
            while (!q.isEmpty() && q.peek()[0] == idx) {
                int[] a = q.poll();
                if (a[2] == 0) // start of an update range
                    totalIncr += a[1];
                else    // end+1 of an update range
                    totalIncr -= a[1];
            }
            prevIdx = idx;
        }
        return result;
    }
    

    Solution II: Accepted (3ms)

    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        if (length == 0 || updates.length == 0)
            return result;
        for (int[] update : updates) {
            int start = update[0], end = update[1], incr = update[2];
            result[start] += incr;
            if (end + 1 < length) // NOTE: end coulbe the last index on array
                result[end + 1] -= incr;
        }
        for (int i = 1; i < length; result[i] += result[i-1], i++);
        return result;
    }
    

  • 0
    Y

    could you please explain you solution II, I am really confused.
    Thank you so much :)


  • 0
    A

    at the index corresponding to start of update, i add incr; at the index right after the end of update, i subtract incr.
    then we iterate from left to right, value of each element on the result array is the accumulated incrs.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.