I was recently solving a problem (ongoing contest. Will post the link after the contest ends) where I came up with a DP solution where dp[i][j] only depended on dp[][j-1]. Clearly one of the techniques to handle this type of problems is to use 1D array to compute dp[i] in an iterative manner for space optimization.↵
↵
However, in the problem I was solving, even using a 2D array for dp[i][j] would not exceed memory limits. So I solved the problem using a 2D array and the verdict was Time Limit Exceeded.↵
↵
But when I simply changed the 2D array to a 1D array and submitted again, the verdict was Accepted.↵
↵
Why does changing a 2D array to a 1D array provide time complexity optimization too ?
↵
However, in the problem I was solving, even using a 2D array for dp[i][j] would not exceed memory limits. So I solved the problem using a 2D array and the verdict was Time Limit Exceeded.↵
↵
But when I simply changed the 2D array to a 1D array and submitted again, the verdict was Accepted.↵
↵
Why does changing a 2D array to a 1D array provide time complexity optimization too ?
