Most space efficient in C solutions


  • 2
    K

    Dynamically allocate the 2-dimentional array.

    char** summaryRanges(int* nums, int numsSize, int* returnSize) {
    
    char **result = (char **)malloc(sizeof(char *));
    *returnSize = 0;
    int s = 0, e = 0;
    
    while (s < numsSize)
    {
    	if ((e + 1 < numsSize) && (nums[e + 1] == nums[e] + 1))
    		e++;
    	else
    	{
    		if (s == e)
    		{
    			(*returnSize)++;
    			result = (char **)realloc(result, (*returnSize)*sizeof(char *));
    			result[*returnSize - 1] = (char *)malloc(12 * sizeof(char));//integer may have many decimal bits
    			sprintf(result[*returnSize - 1], "%d", nums[s]);
    		}
    		else
    		{
    			(*returnSize)++;
    			result = (char **)realloc(result, (*returnSize)*sizeof(char *));
    			result[*returnSize - 1] = (char *)malloc(25 * sizeof(char)); //integer may have many decimal bits
    			sprintf(result[*returnSize - 1], "%d->%d", nums[s], nums[e]);
    		}
    		s = e + 1;
    		e = s;
    	}
    }
    return result;
    

    }


  • 0
    V

    Good approach. You can further avoid static allocation for the individual arrays by storing in a temp variable the required string and calculating it's length. Below is the snippet with modifications

    ...
            char temp[40]; //Assuming a 64 bit int, the string cannot be more than 40 chars.
    ...
    		if (i == j) //both start and end of range are same i,e only one element in the range
    			sprintf(temp, "%d", nums[i]);
    		else
    			sprintf(temp, "%d->%d", nums[i], nums[j]);
    			
            //Below part of the code is brought out of the above if-else block as it is common.
    		q = (char **) realloc (q, sizeof(char *) * *returnSize); //re-allocate with extra rows
    		q[*returnSize - 1] = (char *) malloc (sizeof(char) * (strlen(temp) + 1)); //size of array is length of temp + 1 for null character
    		strcpy(q[*returnSize - 1], temp);
    ...

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.