Java O(n) time O(k) space


  • 140

    We iterate through the input array exactly once, keeping track of the running sum mod k of the elements in the process. If we find that a running sum value at index j has been previously seen before in some earlier index i in the array, then we know that the sub-array (i,j] contains a desired sum.

    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
        int runningSum = 0;
        for (int i=0;i<nums.length;i++) {
            runningSum += nums[i];
            if (k != 0) runningSum %= k; 
            Integer prev = map.get(runningSum);
            if (prev != null) {
                if (i - prev > 1) return true;
            }
            else map.put(runningSum, i);
        }
        return false;
    }
    

  • 2

    Smart solution! I like it!


  • 0

    @tankztc Thanks!


  • 0
    B

    Great solution! Thanks for sharing!


  • 3
    S

    I can't believe I just needed to get the modulus to get this method to work. I was scratching my head to figure out how to modify the runningSum method to work.

    It looks so simple now. I feel so stupid.

    Any suggestions guys how I can improve. I mean there is this leetcode question which is a variant of this and it asks to make the sum exactly equal to target instead of multiple of it. I used the same method for that problem. However, for this, question I couldn't modify the running sum method to work. I feel dumb


  • 4

    Cool!
    Could you explain

    {{put(0,-1);}};
    

    in

    Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};
    

    ?
    Thanks


  • 14
    D

    The main idea is that (x + n*k) mod k = x ,which x can be 0,1,...,k-1.


  • 4

    @BryanBo.Cao , I think it initialized the map with map.put(0,-1).

    "Double brace initialisation creates an anonymous class derived from the specified class (the outer braces), and provides an initialiser block within that class (the inner braces)." - Quoted from Stackoverflow


  • 2

    @tankztc Cool thanks!
    So we could actually omit the last ';' in

    Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
    

    Anyway, it's just about the syntax.


  • 0

    Nice solution taking advantage of "non-negative integer"!


  • 0
    H

    said in Java O(n) time O(k) space:

    if (prev != null) {
    if (i - prev > 1) return true;
    }

    Sorry, I'm still having trouble understanding this part. Can someone explain why we need to check the indices and what it means?


  • 2

    @huyanhh This is to make sure that the sub-array is of at least length 2.


  • 1
    H

    @compton_scatter

    I'm going through your solution with the input [23, 2, 6, 4, 7], k=6, but it seems like I keep messing up.

    When I'm at index 3, the map looks like {0:-1, 5:0, 1:1} and runningSum should be 5 so I look up 5 in the map, but then doing i-prev gives me 3, which will return true without checking 7, but shouldn't I check the last one as the subarray needs to include the entire array? Where am I getting this wrong?


  • 2

    @huyanhh The sum of subarray [2,6,4] is 12, which is a multiple of 6.


  • 0
    H

    @compton_scatter ohh that makes a lot of sense. Thanks!


  • 0
    J

    Smart...Now that with this solution we even didn't need to consider those annoying corner cases like [0,0] 100 -> true...


  • 2

    @compton_scatter said in Java O(n) time O(k) space:

        if (k != 0) runningSum %= k; 
    

    This is smart.


  • 3

    @shawngao Alternatively, do if (k == 0) k = 0x80000000; before the loop and delete the if (k != 0) :-)


  • 4
    O

    I don't understand that why "running sum value at index j has been previously seen before in some earlier index i in the array" can help us decide there's a desired subarray in it?? Could you please kindly explain it? Thanks much @compton_scatter


  • 57
    D

    @ohuohuo This is one of those magics of remainder theorem :)

    (a+(n*x))%x is same as (a%x)

    For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k. Hope this clarifies your doubt :)


Log in to reply
 

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