Java solution using HashMap with detailed explanation


  • 108
    L

    After solving several "Game Playing" questions in leetcode, I find them to be pretty similar. Most of them can be solved using the top-down DP approach, which "brute-forcely" simulates every possible state of the game.

    The key part for the top-down dp strategy is that we need to avoid repeatedly solving sub-problems. Instead, we should use some strategy to "remember" the outcome of sub-problems. Then when we see them again, we instantly know their result. By doing this, we can always reduce time complexity from exponential to polynomial.
    (EDIT: Thanks for @billbirdh for pointing out the mistake here. For this problem, by applying the memo, we at most compute for every subproblem once, and there are O(2^n) subproblems, so the complexity is O(2^n) after memorization. (Without memo, time complexity should be like O(n!))

    For this question, the key part is: what is the state of the game? Intuitively, to uniquely determine the result of any state, we need to know:

    1. The unchosen numbers
    2. The remaining desiredTotal to reach

    A second thought reveals that 1) and 2) are actually related because we can always get the 2) by deducting the sum of chosen numbers from original desiredTotal.

    Then the problem becomes how to describe the state using 1).

    In my solution, I use a boolean array to denote which numbers have been chosen, and then a question comes to mind, if we want to use a Hashmap to remember the outcome of sub-problems, can we just use Map<boolean[], Boolean> ? Obviously we cannot, because the if we use boolean[] as a key, the reference to boolean[] won't reveal the actual content in boolean[].

    Since in the problem statement, it says maxChoosableInteger will not be larger than 20, which means the length of our boolean[] array will be less than 20. Then we can use an Integer to represent this boolean[] array. How?

    Say the boolean[] is {false, false, true, true, false}, then we can transfer it to an Integer with binary representation as 00110. Since Integer is a perfect choice to be the key of HashMap, then we now can "memorize" the sub-problems using Map<Integer, Boolean>.

    The rest part of the solution is just simulating the game process using the top-down dp.

    public class Solution {
        Map<Integer, Boolean> map;
        boolean[] used;
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            int sum = (1+maxChoosableInteger)*maxChoosableInteger/2;
            if(sum < desiredTotal) return false;
            if(desiredTotal <= 0) return true;
            
            map = new HashMap();
            used = new boolean[maxChoosableInteger+1];
            return helper(desiredTotal);
        }
        
        public boolean helper(int desiredTotal){
            if(desiredTotal <= 0) return false;
            int key = format(used);
            if(!map.containsKey(key)){
        // try every unchosen number as next step
                for(int i=1; i<used.length; i++){
                    if(!used[i]){
                        used[i] = true;
         // check whether this lead to a win (i.e. the other player lose)
                        if(!helper(desiredTotal-i)){
                            map.put(key, true);
                            used[i] = false;
                            return true;
                        }
                        used[i] = false;
                    }
                }
                map.put(key, false);
            }
            return map.get(key);
        }
       
    // transfer boolean[] to an Integer 
        public int format(boolean[] used){
            int num = 0;
            for(boolean b: used){
                num <<= 1;
                if(b) num |= 1;
            }
            return num;
        }
    }
    

    Updated: Thanks for @ckcz123 for sharing the great idea. In Java, to denote boolean[], an easier way is to use Arrays.toString(boolean[]), which will transfer a boolean[] to sth like "[true, false, false, ....]", which is also not limited to how maxChoosableInteger is set, so it can be generalized to arbitrary large maxChoosableInteger.


  • 63
    C

    Brilliant solution!
    I think using Arrays.toString() is better.

    Here is my code:

    public class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if (desiredTotal<=0) return true;
            if (maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return false;
            return canIWin(desiredTotal, new int[maxChoosableInteger], new HashMap<>());
        }
        private boolean canIWin(int total, int[] state, HashMap<String, Boolean> hashMap) {
            String curr=Arrays.toString(state);
            if (hashMap.containsKey(curr)) return hashMap.get(curr);
            for (int i=0;i<state.length;i++) {
                if (state[i]==0) {
                    state[i]=1;
                    if (total<=i+1 || !canIWin(total-(i+1), state, hashMap)) {
                        hashMap.put(curr, true);
                        state[i]=0;
                        return true;
                    }
                    state[i]=0;
                }
            }
            hashMap.put(curr, false);
            return false;
        }
    }
    

    Or, using int is enough.

    public class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if (desiredTotal<=0) return true;
            if (maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return false;
            return canIWin(desiredTotal, maxChoosableInteger, 0, new HashMap<>());
        }
        private boolean canIWin(int total, int n, int state, HashMap<Integer, Boolean> hashMap) {
            if (hashMap.containsKey(state)) return hashMap.get(state);
            for (int i=0;i<n;i++) {
                if ((state&(1<<i))!=0) continue;
                if (total<=i+1 || !canIWin(total-(i+1), n, state|(1<<i), hashMap)) {
                    hashMap.put(state, true);
                    return true;
                }
            }
            hashMap.put(state, false);
            return false;
        }
    }
    

  • 1
    L

    Very smart and detailed explanation.

    I have one quick question regarding the memorization. If we cannot use Map<boolean[], boolean> because of the shallow copy like you said, can we simply use Map<Set<Integer>, boolean>? The Set<Integer> is the set of chosen numbers.

    Thank you so so much.


  • 5
    L

    @LeoM58 After some research, I think your idea is feasible because the HashCode for Set<Object> is the sum of hashcode of it's object, and in this case it can uniquely determine a hash set.

    Here is a small example:

    Map<Set<Integer>, Integer> map = new HashMap<>();
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    set1.add(2);
    set1.add(3);
    map.put(set1, 1);     // put set1 into map
    set2.add(2);
    set2.add(3);
    System.out.print(map.get(set1));       // 1
    System.out.print(map.get(set2));      //  1
    

  • 0
    R

    Thank you for your solution, can you please explain the logic of the helper function? Or point out the invariant?


  • 8
    L

    @Rhodey said in Java solution using HashMap with detailed explanation:

    Thank you for your solution, can you please explain the logic of the helper function? Or point out the invariant?

    Sure.

    First, this helper function has a parameter desiredTotal, and it determines that if a player plays first with such a desiredTotal, can s/he win?

    Then it comes to how to decide whether s/he can win.

    The strategy is we try to simulate every possible state. E.g. we let this player choose any unchosen number at next step and see whether this leads to a win. If it does, then this player can guarantee a win by choosing this number. If we find that whatever number s/he chooses, s/he won't win the game, then we know that s/he is guarantee to lose given such a state.

    See explanations below:

           // try every unchosen number as next step
              for(int i=1; i<used.length; i++){
                    if(!used[i]){
                        used[i] = true;
                        // check whether this lead to a win, which means helper(desiredTotal-i) must return false (the other player lose)
                        if(!helper(desiredTotal-i)){
                            map.put(key, true);
                            used[i] = false;
                            return true;
                        }
                        used[i] = false;
                    }
                }
                map.put(key, false);
    

  • 0
    R

    @leogogogo Very detailed and understandable answer! Thank you so much!


  • 0
    L

    @leogogogo Thank you so much for your time and help. It means a lot. I tried the set idea and it is too slow. I guess it's because the frequent copy of sets and space issue.
    Inspired by your idea and code, I finished my version. Thank you again.

    public class Solution {
        int n;
        public boolean canIWin(int newN, int target) {
            n = newN;
    		if (target > n * (n + 1) / 2) {
    		    return false;
    		}
    		Map<Integer, Boolean> memo = new HashMap<>();
    	    return helper(0, memo, target);
    	}
    	private boolean helper(int visiting, Map<Integer, Boolean> memo, int target) {
    	    if (memo.get(visiting) != null) {
    	        return memo.get(visiting);
    	    }
    	    
    	    for (int i = n ; i >= 1 ; i --) {
    	        int choice = 1 << i;
    	        if ((visiting & choice) == 0) {
    	            if (i >= target) {
    	                memo.put(visiting, true);
    	                return true;
    	            }
    	            visiting += choice;
    	            boolean nextWinner = helper(visiting, memo, target - i);
    	            visiting -= choice;
    	            
    	            if (!nextWinner) {
    	                memo.put(visiting, true);
    	                return true;
    	            }
    	        }
    	    }
    	    memo.put(visiting, false);
    	    return false;
    	}
    }

  • 0
    L

    @LeoM58 It's grad to see that!


  • 0
    L

    @leogogogo Thanks again for your timely replay. Can you teach me how to post code? I typed ``` and copied all my code there. But they do not seem to align automatically.


  • 0
    L

    @LeoM58 Yeah, sometimes the code doesn't align automatically, so I just manually add some space for better appearance.


  • 0
    W

    Hi @leogogogo, thank you for your post. May I ask what else "game playing" problems in LC can also solved by top down DP. I want to do more practice. Thank you!


  • 1
    L

    @wondershow like Flip Game II, Burst Balloons , they all can be solved with top-down dp


  • 9
    T

    @ckcz123
    you can just use int state as the key, absolutely faster and shorter.

    public class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if (desiredTotal <= 0) return true;
            if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
            return canIWin(maxChoosableInteger, desiredTotal, 0, new HashMap <> ());
        }
    
        private boolean canIWin(int length, int total, int state, HashMap <Integer, Boolean> hashMap) {
            if (hashMap.containsKey(state)) return hashMap.get(state);
            for (int i = 0; i < length; i++) {
                if ((1 << i & state) == 0) {
                    if (total <= i + 1 || !canIWin(length, total - (i + 1), 1 << i | state, hashMap)) {
                        hashMap.put(state, true);
                        return true;
                    }
                }
            }
            hashMap.put(state, false);
            return false;
        }
    }
    

  • 0
    This post is deleted!

  • 0
    B

    Hi,
    In your post, you mentioned that time complexity will transformed from "exponential to polynomial."
    My thought is that there is still 2^n possible boolean[]used array and 2^n possible key in the hashmap. Could you explain a little bit more about the polynomial time complexity? Thanks!


  • 0
    L
    This post is deleted!

  • 1
    B

    @leogogogo
    Hi,
    In the p("leet") problem there, there are 4 possible subproblems p("eet"),p("et"),pt("t") and p(""). So using the memo schema would lower the bound to polynomial (or proportional to the length of the given string).
    However, in this problem, there are possibly 2^n possible boolean[]used, the subproblem size is scaled to 2^n here. The memo process will lower the time complexity of every subproblem to exactly O(1) and the altogether should be O(2^n). However, the memo process will lower the complexity than the brute force which may cost more.


  • 0
    L

    @billbirdh Well it seems that you are right, because there are O(2^n) combinations, and by using memo we only calculate for each combination at most once. I will update my answer, thanks.


  • 0
    L

    @billbirdh By the way, without memo, what is the time complexity?


Log in to reply
 

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