Missing Numbers

  • + 0 comments

    Hash map and reallocate array

    1. Time Complexity: O(n)
    2. Space Complexity: O(n)
    int find_min(int* arr, int arr_count){
        int min_num = arr[0];
        for (int i=1; i<arr_count; i++){
            if(arr[i] < min_num){
                min_num = arr[i];
            }
        }
        return min_num;
    }
    
    int* append(int* arr, int* size, int number){
        int new_size = *size+1;
        arr = (int* )realloc(arr, new_size*sizeof(int));
        arr[*size] = number;
        *size = new_size;
        return arr;
    }
    
    int* missingNumbers(int arr_count, int* arr, int brr_count, int* brr, int* result_count) {
        // Initialize NULL pointer
        int* res_arr = NULL;
        *result_count = 0;
        
        // find brr minimum element
        int brr_min = find_min(brr, brr_count);
        // initialize the array with zeros
        int* brr_freq = (int* )calloc(100, sizeof(int));
        
        for (int i = 0; i<brr_count; i++){
            brr_freq[brr[i]-brr_min] ++;
        }    
        for (int i = 0; i< arr_count; i++){
            brr_freq[arr[i]-brr_min] --;
        }
        for (int i = 0; i<100; i++){
            if (brr_freq[i] != 0){
                res_arr = append(res_arr, result_count, (i+brr_min));
            }
        }
        return res_arr;
    }