Interview Preparation
Let me clarify the question once ...\ntestcase\nconstraints :\n2 <= n <= 28\n1 <= firstPlayer < secondPlayer <= n\nGive me a few minutes to think it through\nco
Let me clarify the question once ...\ntestcase\nconstraints :\n2 <= n <= 28\n1 <= firstPlayer < secondPlayer <= n\nGive me a few minutes to think it through\ncomment - BF, optimal\ncode\n\n# Intuition\nrecursion -> memoization\n\n# Approach - optimal memoization\n\n# Complexity\n- Time complexity:\n$$O(n^3)$$\n\n- Space complexity:\n$$O(n^3)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int mini=INT_MAX, maxi = INT_MIN; \n    bool visited[27][27][27]={};\n    void dfs(int mask, int round, int i, int j, int first, int second, int l, int m, int r) {\n        if(i>=j) {\n            dfs(mask, round+1, 0, 27, first, second, l, m, r);\n        } else if ((mask & (1<<i)) == 0) {\n            dfs(mask, round, i+1, j, first, second, l, m, r);\n        }else if((mask &(1<<j)) == 0) {\n            dfs(mask, round, i, j-1, first, second, l, m, r);\n        }\n        else if( i== first && j == second) {\n            mini = min(mini, round);\n            maxi = max(maxi, round);\n        } else if(!visited[l][m][r]) {\n            visited[l][m][r] = true;\n            if( i != first && i != second) {\n                dfs(mask^(1<<i), round, i+1, j-1, first, second, l-(i<first), m-(i>first && i<second), r-(i>second));\n            }\n            if(j!=first && j!= second) {\n                dfs(mask^(1<<j), round, i+1, j-1, first, second, l-(j<first), m-(j>first && j<second), r-(j>second));\n            }\n        }\n    }\n    vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {\n        dfs((1<<n)-1, 1, 0, 27, firstPlayer-1, secondPlayer-1, firstPlayer-1, secondPlayer-firstPlayer-1, n-secondPlayer);\n        return {mini, maxi};\n    }\n};\n```\n\n# Approach - recursion(brute force)\n\n# Complexity\n- Time complexity:\n$$O(2^n)$$\n\n- Space complexity:\n$$O(log n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int mini=INT_MAX, maxi = INT_MIN; \n    void dfs(int mask, int round, int i, int j, int first, int second) {\n        if(i>=j) {\n            dfs(mask, round+1, 0, 27, first, second);\n        } else if ((mask & (1<<i)) == 0) {\n            dfs(mask, round, i+1, j, first, second);\n        }else if((mask &(1<<j)) == 0) {\n            dfs(mask, round, i, j-1, first, second);\n        }\n        else if( i== first && j == second) {\n            mini = min(mini, round);\n            maxi = max(maxi, round);\n        } else {\n            if( i != first && i != second) {\n                dfs(mask^(1<<i), round, i+1, j-1, first, second);\n            }\n            if(j!=first && j!= second) {\n                dfs(mask^(1<<j), round, i+1, j-1, first, second);\n            }\n        }\n    }\n    vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {\n        dfs((1<<n)-1, 1, 0, 27, firstPlayer-1, secondPlayer-1);\n        return {mini, maxi};\n    }\n};\n```
['C++']