Skip to content
TheChatArchiveThe Chat Archive
chatgpt-4o-latest-20250326· OpenAIHugging Face LMArena Human Preference 140K

With the C algorithm, could you please optimise it to use less memory?

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-3-5-haiku-20241022’s answer.
  1. User

    With the C algorithm, could you please optimise it to use less memory?

  2. Assistant

    Yes, certainly! The current C implementation uses extra memory to create a new array of structs (NumWithIdx) that pairs each number in the input array with its original index. While this is clean and functional, it essentially duplicates the nums array, consuming O(n) additional memory.

    We can optimize the memory usage by instead of duplicating the full array, using an array of indices only, and sorting those indices based on the values they point to in the original nums array. This way:

    • We avoid duplicating the values (saving memory).
    • We only store pointers (indexes), so the auxiliary array is significantly smaller.

    ✅ Optimized C Implementation (Using Index Array Only)

    #include <stdlib.h>
    
    int compareIndices(const void *a, const void *b, void *nums) {
        int indexA = *(const int *)a;
        int indexB = *(const int *)b;
        int *arr = (int *)nums;
        return arr[indexA] - arr[indexB];
    }
    
    int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
        int *indices = (int *)malloc(numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {
            indices[i] = i;
        }
    
        // Sort indices based on the values they point to in nums[]
        qsort_r(indices, numsSize, sizeof(int), compareIndices, nums);
    
        int left = 0, right = numsSize - 1;
        while (left < right) {
            int sum = nums[indices[left]] + nums[indices[right]];
            if (sum == target) {
                int *result = (int *)malloc(2 * sizeof(int));
                result[0] = indices[left];
                result[1] = indices[right];
                *returnSize = 2;
                free(indices);
                return result;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    
        free(indices);
        *returnSize = 0;
        return NULL;  // No result found; shouldn't happen due to problem constraints.
    }
    

    🔍 Key Improvements

    • Reduced memory usage: Instead of duplicating the entire array as structs, we only allocate an array of indices: int indices[n].
    • qsort_r: We're using qsort_r (reentrant quicksort) to allow passing an extra argument (nums) to compare function for sorting based on values. If qsort_r isn't available, we can simulate with global access (less thread-safe).
    • Maintains O(n log n) time complexity due to sorting.

    💡 This code assumes qsort_r is available. If not, or if using environments like MSVC on Windows, we can adapt using other approaches (e.g. global array or qsort_s for Microsoft).


    Alternative if qsort_r is not available

    You can use a global pointer to access nums inside the compare function, but this is less elegant and not thread-safe:

    int *globalNums;
    
    int compareIndicesGlobal(const void *a, const void *b) {
        int indexA = *(const int *)a;
        int indexB = *(const int *)b;
        return globalNums[indexA] - globalNums[indexB];
    }
    
    // In main function
    globalNums = nums;
    qsort(indices, numsSize, sizeof(int), compareIndicesGlobal);
    

    ⚙️ Time and Space Complexity

    • Time: O(n log n) due to sorting.
    • Space: O(n), reduced from previous O(n) of full struct to just O(n) for indices (lighter).

    Let me know if you’d like an even more memory-constrained version (e.g. maintaining a single result variable only), or a pure in-place solution using modification of the input array.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.