Generic sweep line algorithm, O(n + k) time complexity and O(1) space complexity


  • 1
    T

    When I tried to solve this question, I didn't come up with the trick:(. But still, I got it solved with the generic sweep line algorithm, which is just to split intervals into end points. Again, the code looks more complex than the one solved with tricks, but it gives a generic solution to solve nearly all interval questions with sweep line algorithm even if you don't know the trick. But could anyone who solved it with the trick tell me how do you guys think of the trick, I mean, in a general way, when approach this kind of question? Thanks!

    public class Solution {
    class Wrapper {
        int value;
        int type;
        int index;
        int inc;
        public Wrapper(int value, int type, int index, int inc) {
            this.value = value;
            this.type = type;
            this.index = index;
            this.inc = inc;
        }
    }
    public int[] getModifiedArray(int length, int[][] updates) {
        //check edge case
        if (updates == null || updates.length == 0 || updates[0].length == 0) {
            return new int[1];
        }
        //preprocess
        int[] result = new int[length];
        //scan line
        int k = updates.length;
        ArrayList<Wrapper> wrappers = new ArrayList<Wrapper>();
        for (int i = 0; i < k; i++) {
            wrappers.add(new Wrapper(updates[i][0], 0, i, updates[i][2]));
            wrappers.add(new Wrapper(updates[i][1], 1, i, updates[i][2]));
        }
        Comparator<Wrapper> cmp = new Comparator<Wrapper>(){
            public int compare(Wrapper a, Wrapper b) {
                if (a.value < b.value) {
                    return -1;
                } else if (a.value > b.value) {
                    return 1;
                } else {
                    if (a.type < b.type) {
                        return -1;
                    } else if (a.type > b.type) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        };
        //sort
        Collections.sort(wrappers, cmp);
        int j = 0;
        int curInc = 0;
        for (int i = 0; i < length; i++) {
          result[i] += curInc;
          while (j < wrappers.size() && wrappers.get(j).value <= i) {
            Wrapper wrapper = wrappers.get(j);
            if (wrapper.type == 0) {
                result[i] += wrapper.inc;
                curInc += wrapper.inc;
            }else {
                curInc -= wrapper.inc;
            }
            j++;
          }  
        }
        return result;
    }
    

    }


  • 0

    Not an O(N+K) running time any more if sorting is involved.
    Your solution should be O(N + K + K log K) more precisely.


Log in to reply
 

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