Java and python DP solution O(nk)


  • 0
    V

    The idea is to keep all possible sums for nums[i] and generate all possible sums for nums[i+1] using + and -.

    Python

    def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            if len(nums)==0:
                return 0
            from collections import defaultdict
            prev = defaultdict(int)
            prev[nums[0]] += 1
            prev[-nums[0]] += 1
            
            for i in range(1, len(nums)):
                temp = defaultdict(int)
                for k,v in prev.items():
                    temp[k-nums[i]]+=v
                    temp[k+nums[i]]+=v
                prev = temp
            return prev[S]
    

    JAVA

    public int findTargetSumWays(int[] nums, int S) {
            if(nums.length==0) return 0;
            Map<Integer, Integer> prev = new HashMap<Integer, Integer>();;
            Map<Integer, Integer> cur;
            for(int i = 0; i< nums.length; i++){
                //for nums[0]
                if(i==0){
                    prev.put(nums[0], 1);
                    if(!prev.containsKey(-nums[0])){
                        prev.put(-nums[0], 1);
                    }else{
                        prev.put(-nums[0], 2); // if nums[0] is 0.
                    }
                }else{
                    cur = new HashMap<Integer, Integer>();
                    for(Map.Entry<Integer, Integer> entry: prev.entrySet()){
                        int sumSoFar = entry.getKey();
                        int count = entry.getValue();
                        // add num[i]
                         if(!cur.containsKey(sumSoFar+nums[i])){
                             cur.put(sumSoFar+nums[i], count);
                         }else{
                             cur.put(sumSoFar+nums[i], cur.get(sumSoFar+nums[i])+count);
                         }
                         // subtract num[i]
                         if(!cur.containsKey(sumSoFar-nums[i])){
                             cur.put(sumSoFar-nums[i], count);
                         }else{
                             cur.put(sumSoFar-nums[i], cur.get(sumSoFar-nums[i])+count);
                         }
                    }
                    prev = cur;
                }
            }
            return prev.containsKey(S)? prev.get(S) : 0;
        }
    

  • 0

    You claim this is O(n) in time?


  • 0

    If this is O(n), you will win a Turing award!


  • 0
    V

    @jedihy I apologize. It's O(nk) because HashMap size is also growing.


  • 0

    @varun37 No Problem. The time complexity I believe is O(nS) where S is the target.


Log in to reply
 

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