Prefix sums in 3 languages (Python, Java and C)


  • 0
    D

    My Python solution with prefix sums: it explores all the O(n^2) subarrays,
    but evaluates each subarray [i,j] efficiently in O(1) time with the formula
    psum[j] - psum[i]. Sadly, this times out due the language chosen.

    See the Java and C ports of the same algorithm (on this same directory),
    they get both accepted. Interestingly the Java version runs twice as fast as
    the C version! I never thought that I would see the say when C was
    outperformed by Java ;-?

    Python (time out):

    class Solution(object):
        def calc_psum(self, nums, n):
            psum = [0] * n
            psum[0] = nums[0]
            for i in xrange(1, n):
                psum[i] = psum[i - 1] + nums[i]
            return psum
    
        def subarraySum(self, nums, k):
            n = len(nums)
            if n == 0:
                return 0
            psum = self.calc_psum(nums, n)
            cnt = 0
            for i in xrange(n):
                for j in xrange(i, n):
                    if psum[j] - (psum[i-1] if i > 0 else 0) == k:
                        cnt += 1
            return cnt
    

    Java (accepted ~ 200 ms):

    class Solution {
        public int subarraySum(int[] nums, int k) {
            int n = nums.length;
            if (n == 0)
                return 0;
            int[] psum = new int[n];
            psum[0] = nums[0];
            for(int i=1; i<n; i++)
                psum[i] = psum[i-1] + nums[i];
            int cnt = 0;
            for(int i=0; i<n; i++)
                for(int j=i; j<n; j++)
                    if (psum[j] - (i>0? psum[i-1] : 0) == k)
                        cnt += 1;
            return cnt;
        }
    }
    

    C (accepted ~ 400 ms)

    #include <stdlib.h>
    
    int subarraySum(int* nums, int numsSize, int k) {
        int n = numsSize;
        if (n == 0)
            return 0;
        int * psum = (int *) malloc(sizeof(int)*n);
        psum[0] = nums[0];
        for(int i=1; i<n; i++)
            psum[i] = psum[i-1] + nums[i];
        int cnt = 0;
        for(int i=0; i<n; i++)
            for(int j=i; j<n; j++)
                if (psum[j] - (i>0? psum[i-1] : 0) == k)
                    cnt += 1;
        return cnt;
    }
    

Log in to reply
 

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