I tried to solve the below problem in Python and C as well:
Written the below solution using ‘extend’/’+’ and append operations:
This solution took more time because of ‘+’ and append operations.
Thought let me create 2d array, then fill the values, where there are no ‘append’ and ‘extend’ operations are required. Surprisingly the execution time of this solution is lesser compared to the above. Below is the optimized solution I observed:
Any other ideas on how to optimize more. Please share your comments.
In C, I tried using memcpy to avoid multiple iterations:
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** matrixReshape(int** mat, int matSize, int* matColSize, int r, int c, int* returnSize, int** returnColumnSizes){
int **res, row, col, cr, cc, tmp_size,nc;
int *col_sizes;
if ((matSize * (*matColSize)) != (r * c))
{
*returnSize = matSize;
*returnColumnSizes = matColSize;
return mat;
}res = (int **)malloc(r*sizeof(int *));
if (!res)
return NULL;
*returnColumnSizes = (int *)malloc(r*sizeof(int));
if (!(*returnColumnSizes))
{
free(res);
return NULL;
}
for (row=0; row < r; row++)
{
res[row] = (int *)malloc(c*sizeof(int));
(*returnColumnSizes)[row] = c;
if (!res[row])
return NULL;
}
row = col = cr = cc = 0;
/*max num of elements which can copied at a time */
if ((*matColSize) < c)
tmp_size = *matColSize;
else
tmp_size = c;
while (row < matSize && col < *matColSize)
{
nc = tmp_size;
/* how many max can be copied from mat at a time */
if ((col + tmp_size) >= *matColSize)
nc = (*matColSize) — col;/* how many max can be copied to res at a time */
if ((cc + nc) >= c)
nc = c — cc;//printf(“col %d, row %d, cur-row %d, cur-col %d, nc %d\n”, col, row, cr, cc, nc);
memcpy(&res[cr][cc], &mat[row][col], nc*sizeof(int));
col += nc;
cc += nc;
if (col == *matColSize)
{
row ++;
col = 0;
}
if (cc == c)
{
cr ++;
cc = 0;
}
//printf(“col %d, row %d, cur-row %d, cur-col %d, nc %d\n”, col, row, cr, cc, nc);
}
/*
printf(“input matrix:\n”);
for (row = 0; row < matSize; row++)
{
for (col = 0; col < *matColSize; col++)
printf(“%d “, mat[row][col]);
printf(“\n”);
}
printf(“\n res matrix:\n”);
for (row = 0; row < r; row++)
{
for (col = 0; col < c; col++)
printf(“%d “, res[row][col]);
printf(“\n”);
}
*/
*returnSize = r;
//*matColSize = c;
return res;
}
Not sure if memcpy is better or more iterations are better. Please share your opinions.
