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

• ``````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];
}
};
``````

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