Java O(n+k) time O(1) space with algorithm explained


  • 13

    segment [i,j] is made of two parts [0,i-1] and [0, j]
    so [i,j] increase 2 is same as [0,j] increase 2 and [0,i-1] increase -2. so you only need to update value at nums[j] with inc and nums[i-1] -inc. initially nums[i] is defined as all elements [0,i] increases inc

    then think from length-1 to 0 backward. The last spot nums[length-1] does not need any modification.
    nums[length-2] value should be updated as nums[length-2] + nums[length-1] as the latter covers the front. but front does not influence what is after it. so every spot should be updated as + the accumulate sum from the end.

    public class Solution {
        public int[] getModifiedArray(int length, int[][] updates) {
            int[] nums = new int[length];
            for (int[] update : updates) {
                nums[update[1]] += update[2];
                if (update[0] > 0) {
                    nums[update[0] - 1] -= update[2];
                } 
            }
            
            int sum = nums[length - 1];
            for (int i = length - 2; i >= 0; i--) {
                int tmp = sum + nums[i];
                nums[i] += sum;
                sum = tmp; 
            }
            return nums;
        }
    }

  • 0
    I

    How did you come up with this? I could not come up with this even after looking at all the hints, it seems pretty impossible to do this in interview...


  • 0

    @IWantToPass This question is indeed tricky. I thought the hints were helpful. Is there any more hints that you think should be included?


  • 0
    I

    To be honest I'm not sure what other hints you could give; I feel as if this would be a "Hard" question as opposed to medium though, but that is just my opinion. I am just very nervous that I will not be able to pass google's interview, since I could only do this in the brute force way.


  • 0

    @IWantToPass You are definitely not alone, as many other people also share the same thought as you. I have changed the problem difficulty to "Hard".


  • 0

    @IWantToPass it took me about 15
    mins to think of the approach after seeing the hints. I think it is still possible to finish it in interview.


  • 0

    @IWantToPass said in Java O(n+k) time O(1) space with algorithm explained:

    it seems pretty impossible to do this in interview...

    Not impossible but rather trivial. I thought of it instantly. It's a common technique and this problem is a particularly easy variation. Though I admit that xuyirui's explanation and solution in my opinion make it look more complicated than it is.

    Definitely not "hard" category.


  • 0

    @StefanPochmann Definitely easy for you. You have so many amazing tricks and techniques of algorithm and coding. Maybe it be written to a book. I am very interested in buying a Java version of it.


  • 0
    I

    I have never seen this technique being used before, maybe that is why I could not come up with it, idk. In any case I feel screwed for the interview lol :/


  • 0
    I

    @StefanPochmann , what are some other questions that use this trick that you know of? Have you seen other q's that use it in interview setting?


  • 0

    @xuyirui Well yes, I have a decent amount of experience with such problems, so maybe I can't properly judge how easy something is for beginners. On the other hand, I think this same experience does let me properly judge a problem relative to other problems, because I've done so many. And I really think this is a relatively easy one. Write a book? Me? Nah. And certainly not Java. I dislike Java.


  • 7

    @IWantToPass A slightly harder one is Meeting Rooms II and a significantly harder one is The Skyline Problem.

    Let me describe the technique in my own words:

    Go from the left end to the right end, holding some current status and update that status at certain points. For example in this problem, the status is the current array value. If the input has no operations, then you just walk from start to end and write "0" everywhere. But what if there's one operation, [startIndex=100, endIndex=200, inc=33]? Then you only write "0" until index 100, then you write "33" until index 200, and then you write "0" until the end. In other words, you start off writing "0", until something happens. You encounter the beginning of an operation. So you increase your status to "33" and keep writing that. Until the next event, which in this case is the end of that operation, so you decrease your status by 33 back to "0" and then keep writing that until the end.

    The first half of xuyirui's solution (and pretty much everybody's, because it's the common and obvious way to do it) collects all these events, storing at what points we'll change the "current status value" and how we'll change it. And then the second half of the solution just does the walk, updating the "current status value" with the collected event data, and storing it in the output.

    Would IMHO be a little clearer to go forwards and to use a separate array for the events data, which could also have a more appropriate name, like "increaseBy". (Then it's of course it's not O(1) extra space anymore, but that wasn't required, and it's also really not hard to go from separate array to reused array.)


  • 9

    Here's an implementation that I think is clearer. I even went so far to use separate increase/decrease data. Let me know what you think about it.

    def getModifiedArray(self, length, updates):
        
        # Collect the events, i.e., what changes happen and when they happen
        increaseAt = [0] * length
        decreaseAfter = [0] * length
        for start, end, inc in updates:
            increaseAt[start] += inc
            decreaseAfter[end] += inc
    
        # Sweep, i.e., walk the range, updating the current value and storing it in the output array
        outputArray = [None] * length
        currentValue = 0
        for index in range(0, length):
            currentValue += increaseAt[index]
            outputArray[index] = currentValue
            currentValue -= decreaseAfter[index]
    
        # Ship it
        return outputArray
    

    (Note this is Python, though intentionally not written as pythonically as I could, to be clearer for people not so familiar with Python.)


  • 0
    I

    @StefanPochmann thanks for this implementation :)


  • 0
    I

    @StefanPochmann so increaseAt[start] means "increase all the values from start onwards with this amount, right?


  • 0

    @IWantToPass I guess you can think of it that way, yes. But it seems confusing to me. I really just think of it as "increase the status value at this point".


  • 1
    S

    Thanks for your sharing and explanation!
    Just wanted to point out your second loop can be further simplified:

    public class Solution {
        public int[] getModifiedArray(int length, int[][] updates) {
            int[] nums = new int[length];
            for (int[] update : updates) {
                nums[update[1]] += update[2];
                if (update[0] > 0) {
                    nums[update[0] - 1] -= update[2];
                } 
            }
            
            for (int i = length - 2; i >= 0; i--) {
                nums[i] += nums[i + 1];
            }
            return nums;
        }
    }
    

  • 0

    @snowcat thanks, i realized that.


  • 3
    A

    In a signal processing way of thinking...
    Your output array is like a function f(x) = f1(x) + f2(x) + ... + fn(x) where x is the index.
    where fi(x) is a modification to the array with a format like [0 0 0 ... k k k ... 0 0 0]
    So taking fi(x) 's differentiation you get [0 0 0 +k 0 0 0 ... -k 0 0 0 ] where the -k locates at one behind the stopping index. (Pulses !!)
    f'(x) = f1'(x) + f2'(x) + ... + fn'(x) which gets you the array in which you "only apply the update to the start and end indexes".
    So applying an integral on f'(x), you get the result array.

    Miss the old days thinking EE stuff.


  • 1
    G

    @StefanPochmann This is not an easy question nor it is medium.

    1. It requires knowledge of the sweepline Algo.
    2. It requires to use the sweepline in a modified (hacky) way.
      Coming up with the two in an interview context for someone who isn't familiar with (1), is almost impossible.

    In general, it seems to me that Google is raising the bar continuously. This is the kind of problems I would expect a coding competitor to be able to handle well, but someone else not so much.


Log in to reply
 

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