Consider a matrix of size n, consisting of lower case aplhabets. We are required to find lexicographically smallest string starting from (1,1) and ending at (n,n).

Now it is easily solvable in O(n^3) time ans space , but it is required to solve it in O(n^2) both time and space. Any help is appreciated