C++ (3ms) with Memoization, recursive thought process


  • 0
    N
    class Solution {
    public:
    	bool PredictTheWinner(vector<int>& nums) {
    		if (nums.size() <= 1)
    			return true;
    		// key: int representation of num where left and right range position bits are set
    		// value: first,second player score , maximizing player 1 score
    		unordered_map<int, pair<int, int>> cache;
    		pair<int, int> ret = helper(cache, nums, 0, nums.size() - 1);
    		return ret.first >= ret.second; // >= as in case of tie also player 1 wins
    	}
    
    private:
    	pair<int, int> helper(unordered_map<int, pair<int, int>>& cache, const vector<int>& nums, int l, int r) {
                    // Make the key by setting the bit at the left and right position
    		int key = (1 << (nums.size() - 1 - l)) | (1 << (nums.size() - 1 - r));
            
    		auto it = cache.find(key);
    		if (it != cache.end()) {
    			return it->second;
    		}
    
                    // Base case when there are only 2 elements to choose from
    		if (l + 1 == r) {
    			cache[key] = pair<int, int>(max(nums[l], nums[r]), min(nums[l], nums[r]));;
    			return cache[key];
    		}
    		// the returned score for player one will be second one
    		// as player two will choose in such a way that he/she wins
    		pair<int, int> leftScore = helper(cache, nums, l + 1, r);
    		pair<int, int> rightScore = helper(cache, nums, l, r - 1);
    
    		// update left and right score to reflect current player wining
                    // current player score will be what best he/she got given player2 was playing first
                    // after player 1 choosing value left or right + nums[left or right]
    		int tempSecondPlayerScore = leftScore.first;
    		leftScore.first = leftScore.second + nums[l];
    		leftScore.second = tempSecondPlayerScore;
    
    		tempSecondPlayerScore = rightScore.first;
    		rightScore.first = rightScore.second + nums[r];
    		rightScore.second = tempSecondPlayerScore;
    
    		leftScore.first >= rightScore.first ? cache[key] = leftScore : cache[key] = rightScore;
    		return cache[key];
    	}
    };
    

Log in to reply
 

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