O(n) time, O(k) space, 10 ms Java


  • 0
    N

    The code first checks if k is zero. If it is, the only case that would return true is if there were at least two consecutive zeros. If, however, k is not zero, iterate through the list and calculate the cumulative "mod sum" up to index i (i.e. cumulative sum MOD k). If we've seen this mod sum before, then it means we have a contiguous subarray whose sum MOD k is zero.

    public boolean checkSubarraySum(int[] nums, int k) {
            if (k == 0) {
                boolean prevZero = false;
                for (int i=0; i<nums.length; i++) {
                    if (prevZero && nums[i] == 0) return true;
                    prevZero = nums[i] == 0;
                }
            } else {
                Set<Integer> remainders = new HashSet<>();
            
                int modSum = 0;
                for (int i=0; i<nums.length; i++) {
                    modSum = (modSum + nums[i]) % k;
                    if (modSum == 0 && i != 0) return true;
                    if (remainders.contains(modSum)) return true;
                    remainders.add(modSum);
                }
            }
            
            return false;
        }
    

  • 0
    D

    @nkdl2017 said in O(n) time, O(k) space, 10 ms Java:

    The code first checks if k is zero. If it is, the only case that would return true is if there were at least two consecutive zeros.

    What about the case when the input array is [-1, -2, +1, +2] and k = 0? Shouldn't the answer returntrue?


  • 1
    N

    @dribvurhd the problem statement says that the array only contains non-negative numbers.


  • 0
    D

    @dribvurhd the problem statement says that the array only contains non-negative numbers.

    ugh. seem to have missed that. Sorry :-/


Log in to reply
 

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