int[] vs ArrayList<>() in memoization, dynamic programming in Java

Question

I recently watched a dynamic programming tutorial on Youtube explaining dynamic programming but the Tutor solved problems in JavaScript. I, on the other hand, use Java for data structures and algorithms. While implementing dynamic programming to solve a question. I discovered that I got the solution to the problem when using int[] but had wrong answer when using ArrayList<Integer> because somehow, the ArrayList already stored in the HashMap was being modified internally.

Question: Write a function bestSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments and returns an array containing the shortest combination of numbers that add up to exactly the target sum.
Example:
bestSum(7,new int[]{2,1,3}) => [3,3,1] //other possibilities but not answer:[2,2,2,1], [1,1,1,1,1,1,1], [2,2,1,1,1], etc
bestSum(100,new int[]{2,5,25}) => [25,25,25,25]

Code using int[]:

public class Persist {
    public static HashMap<Integer,int[]> memo = new HashMap<>();
    public static int[] bestSum(int n, int[] arr){
        if(memo.containsKey(n)){
            //System.out.printf("From memo: %d->"+ Arrays.toString(memo.get(n)) +"%n",n);
            return memo.get(n);
        }

        if(n==0)return new int[0];

        if(n<0)return null;

        int[] minn = null;

        for(int i = 0;i<arr.length;i++){
            
            //recursion
            var temp = bestSum(n-arr[i],arr);

            if(temp!=null){

                // ttemp is used to add arr[i] to the initial arr <<temp>>
                int[] ttemp = new int[temp.length+1];
                System.arraycopy(temp,0,ttemp,0,temp.length);
                ttemp[temp.length] = arr[i];
                temp = ttemp;

                if(minn==null||temp.length<minn.length){
                    minn = temp;
                }
            }
        }
        //System.out.println(n+": "+minn);
        memo.put(n,minn);
        //System.out.println(memo.get(n));
        return minn;
    }
    public static void main(String[] args){
        System.out.println(Arrays.toString(bestSum(7, new int[]{2,1,3})));
    }
}

Code using ArrayList<Integer> :

public class Persist {
    public static HashMap<Integer,ArrayList<Integer>> memo = new HashMap<>();
    public static ArrayList<Integer> bestSum(int n, int[] arr){
        if(memo.containsKey(n)){
            //System.out.printf("From memo: %d->"+ memo.get(n)+"%n",n);
            return memo.get(n);
        }
        if(n==0)return new ArrayList<>();
        if(n<0)return null;
        ArrayList<Integer> minn = null;
        for(int i = 0;i<arr.length;i++){
            var temp = bestSum(n-arr[i],arr);
            if(temp!=null){
                temp.add(arr[i]);
                if(minn==null||temp.size()<minn.size()){
                    minn = temp;

                }
            }
        }
        //System.out.println(n+": "+minn);
        memo.put(n,minn);
        //System.out.println(memo.get(n));
        return minn;
    }
    public static void main(String[] args){
        System.out.println(bestSum(7,new int[]{2,1,3}));
    }
}

The only differences between the two code snippets is the use of int[] and ArrayList<Integer> respectively, but one works and the other doesn't. I will like to know why, thanks. Link to Youtube explanation of bestSum()

Remind me, do you get a deep copy when you do memo.put(n, minn);? — Surt
– Surt, Commented Dec 14, 2020 at 1:11
@Surt I did something like this but still got wrong answers as well. memo.put(n,minn==null?null:new ArrayList<>(minn)); — lordvidex
– lordvidex, Commented Dec 14, 2020 at 5:20

mel3kings · Accepted Answer · 2020-12-14 06:37:05Z

2

It's easy to get caught up with memoization and dynamic programming and forget that about pass by reference and pass by value. The key difference here to remember is that ArrayList is pass by reference.

If you debug and look at your hashmap memo, you see that the sizes of the int[] only reaches up to 3, whereas in the arraylist hashmap most of the values has a size of 7

I had a similar problem: casting does not work on nested list object type and returns empty lists (List<List<Integer>>)

answered Dec 14, 2020 at 6:37

mel3kings

9,4603 gold badges65 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

lordvidex Over a year ago

does the same apply for c++?

lordvidex Over a year ago

Also the hashCode() of value of the ArrayList implementation is the same for keys: 5,6,7

Surt Over a year ago

@lordvidex no C++ is copied, unless you specify reference, though the copy is not propagated through pointers unless the appropriate copy constructors are defined.

Collectives™ on Stack Overflow

int[] vs ArrayList<>() in memoization, dynamic programming in Java

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related