# algorithms – Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution and was able to optimise the solution using memoization. The memoized solution is attached below.

``````class Solution {
int tSum(105) = {0};
public:
/**
*  This method returns the maximum number of stones
*  that can be collected where :
*  - idx is the starting index
*  - 2 * m is the maximum size of the window at idx
*/
int util(vector<int>& ar, vector<vector<int>> &dp, int idx, int m)
{
if(dp(idx)(m) != -1)
return dp(idx)(m);

if(idx + (2*m) - 1 >= ar.size())
{
int s = 0;
for(int i=idx; i<ar.size(); i++)
s += ar(i);
return dp(idx)(m) = s;
}

// Total number of stones from idx till the end
int total = idx > 0 ? tSum(ar.size()-1) - tSum(idx-1) : tSum(ar.size()-1);

int nStones = INT_MIN;
for(int i=0; i<(2*m) && (idx+i<ar.size()); i++)
{
// Best number of stones = total stones - best the other player can achieve
nStones = max(nStones, total - util(ar, dp, idx+i+1, max(m, i+1)));
}

return dp(idx)(m) = nStones;
}

int stoneGameII(vector<int>& ar) {
vector<vector<int>> dp(105, vector<int>(105, -1));
tSum(0) = ar(0);
for(int i=1;i<ar.size(); i++)
tSum(i)  = tSum(i-1) + ar(i);
return util(ar, dp, 0, 1);
}
};
``````

However, I am not sure about the time complexity of this solution.

According to me :

• There are `m x n` states, where :
• `n` is the number of elements in `piles` vector.
• `m` is the width of window that varies at each step.
• Each state is being calculated only once.
• `m` can not be greater than `n` i.e the size of `piles`.

Hence, the time complexity of the solution should be `O(n^2)`.

Is there something that I am missing ? Is there a mathematical way to prove this ?

Posted on Categories Articles