C code
Intuition\nIn the intuition method, we can store every number in every snaphot.\nConsequently, we would encounter timeout results.\n\n# Approach\nWe need to use
# Intuition\nIn the intuition method, we can store every number in every snaphot.\nConsequently, we would encounter timeout results.\n\n# Approach\nWe need to use hash table to "only" store value when "set" function has been called.\n\nThis question is very easy when we apply the C++ language.\nHowever, it is very hard by C language, because we have to control the memory usage and allocation. Otherwise, we would get timeout result.\n\n# Complexity\n- Time complexity:\nIn the get function, it would be O(LogN).\nIn the set function, it would be O(1).\n\n- Space complexity:\n\n\n# Code\n```\n\n#define INIT_SNAP_SIZE 10\n\ntypedef struct {\n    int ***table;\n    int *size;\n    int snap_id;\n    int snap_size;\n} SnapshotArray;\n\n\nSnapshotArray* snapshotArrayCreate(int length) {\n    int i, j;\n    SnapshotArray *obj = (SnapshotArray *)malloc(sizeof(SnapshotArray));\n    obj->snap_id = 0;\n    obj->snap_size = INIT_SNAP_SIZE;\n    obj->table = (int ***)malloc(sizeof(int **) * length);\n    for (i=0; i<length; i++) {\n        obj->table[i] = (int **)malloc(sizeof(int *) * obj->snap_size);\n        for (j=0; j<obj->snap_size; j++) {\n            obj->table[i][j] = calloc(2, sizeof(int));\n        }\n    }\n    obj->size = (int *)malloc(sizeof(int) * length);\n    for (i=0; i<length; i++)\n        obj->size[i] = 1;\n    return obj;\n}\n\nvoid snapshotArraySet(SnapshotArray* obj, int index, int val) {\n    int i, size = obj->size[index];\n\n    if (obj->table[index][size-1][0] == obj->snap_id) {\n        obj->table[index][size-1][1] = val;\n        return;\n    }\n\n    if (obj->size[index] == obj->snap_size) {\n         obj->table[index] = (int **)realloc(obj->table[index], sizeof(int *) * (obj->snap_size * 2));\n         for (i=obj->snap_size; i<obj->snap_size*2; i++)\n            obj->table[index][i] = calloc(2, sizeof(int));\n\n        obj->snap_size *= 2;\n    }\n\n    obj->table[index][size][0] = obj->snap_id;\n    obj->table[index][size][1] = val;\n    obj->size[index]++;\n}\n\nint snapshotArraySnap(SnapshotArray* obj) {\n    return obj->snap_id++;\n}\n\nint snapshotArrayGet(SnapshotArray* obj, int index, int snap_id) {\n    int left, right, mid;\n\n    left = 0;\n    right = obj->size[index] - 1;\n    while (left < right) {\n        mid = left + (right - left + 1) / 2;\n        if (obj->table[index][mid][0] <= snap_id)\n            left = mid;\n        else\n            right = mid - 1;\n    }\n\n    return obj->table[index][left][1];\n}\n\nvoid snapshotArrayFree(SnapshotArray* obj) {\n    free(obj);\n}\n\n/**\n * Your SnapshotArray struct will be instantiated and called as such:\n * SnapshotArray* obj = snapshotArrayCreate(length);\n * snapshotArraySet(obj, index, val);\n \n * int param_2 = snapshotArraySnap(obj);\n \n * int param_3 = snapshotArrayGet(obj, index, snap_id);\n \n * snapshotArrayFree(obj);\n*/\n```
['C']