# Competitive Coding

## Questions

Container with most water is a brilliant question with an elegant solution that feels like magic. Initial instinct would be to go through the array in O(n^2) time but turns out that it could be brought down to O(n) time and O(1) space complexity. I wish I could classify this problem but I haven't solved these kinda questions enough.

Reveal cards in increasing order is a very good question for testing your knowledge queue implementation.

## Curated Questions

Approach 1 : Recursion
```int retbest(int a,int b,vector A, vector B){
if(a == A.size() || b==B.size()){
return 0;
}

int best = 0;
best = max(best,retbest(a+1,b,A,B));
best = max(best,retbest(a,b+1,A,B));

if (A[a]==B[b]){
best = max(best,retbest(a+1,b+1,A,B)+1);
}
return best;
}
int maxUncrossedLines(vector& A, vector& B) {
return retbest(0,0,A,B);
}
```

Approach 2: Memoization (arrays)
```int memo; // Storing in memory
bool calc; // True if calculated
int retbest(int a,int b,vector A, vector B){
if(a == A.size() || b==B.size()){
return 0;
}

if(calc[a][b]==true){
return memo[a][b]; // Return calculated
}

int best = 0;
best = max(best,retbest(a+1,b,A,B));
best = max(best,retbest(a,b+1,A,B));

if (A[a]==B[b]){
best = max(best,retbest(a+1,b+1,A,B)+1);
}

memo[a][b] = best; // Store calculated value
calc[a][b] = true; // Set as calculated
return best;
}
int maxUncrossedLines(vector& A, vector& B) {
return retbest(0,0,A,B);
}
```

Approach : Memoization (vectors)

```int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
// For memoization.
vector<vector<int>> dp(n1, vector(n2, -1));
int result = cost(word1, word2, n1 - 1, n2 - 1, dp);
return result;
}
int mini(int a, int b, int c) {
return min(min(a, b), c);
}
int cost(string &S, string &T, int i, int j, vector> &dp) {
if (i < 0 || j < 0) {return abs(i - j);} // Insert leftovers
if (dp[i][j] != -1) {return dp[i][j];} // Fetch cache
if (S[i] == T[j]) { // Accept when equal
return dp[i][j] = cost(S, T, i - 1, j - 1, dp); x
}

return dp[i][j] = mini( 1 + cost(S, T, i - 1, j - 1, dp),   // Replacement
1 + cost(S, T, i, j - 1, dp),       // Insertion
1 + cost(S, T, i - 1, j, dp));      // Deletion
}
```

Last Updated: 31 May 2020