We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Stacks
- Maximum Element
- Discussions
Maximum Element
Maximum Element
+ 0 comments My solution in C passed the initial test but gave a compiler message "Abort" on the other tests.
Can someone please help me find the error in my code?
I searched other discussions and any comments posted for C solutions applied to cases where the inputs were captured in main() as opposed to being sent as arguments to the getMax() function.
#include <assert.h> #include <ctype.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_SIZE 100000 typedef struct { int *arr; int size; int top; } Stack; char* readline(); char* ltrim(char*); char* rtrim(char*); int parse_int(char*); int isEmpty(Stack *s); int isFull(Stack *s); void push(Stack *s, int data); int pop(Stack *s); int maximum(Stack *s); int isEmpty(Stack *s) { if (s->top == -1) return 1; return 0; } int isFull(Stack *s) { if (s->top == s->size - 1) return 1; return 0; } void push(Stack *s, int data) { if (!isFull(s)) { s->top++; s->arr[s->top] = data; } else { printf("Error: stack overflow\n"); } } int pop(Stack *s) { int ans = -1; if (isEmpty(s)) { printf("Error: No element to pop\n"); } else { ans = s->arr[s->top]; s->top--; } return ans; } int maximum(Stack *s) { int max = s->arr[0]; for (int i = 0; i <= s->top; i++) { if (max < s->arr[i]) max = s->arr[i]; } return max; } /* * Complete the 'getMax' function below. * * The function is expected to return an INTEGER_ARRAY. * The function accepts STRING_ARRAY operations as parameter. */ /* * To return the integer array from the function, you should: * - Store the size of the array to be returned in the result_count variable * - Allocate the array statically or dynamically * * For example, * int* return_integer_array_using_static_allocation(int* result_count) { * *result_count = 5; * * static int a[5] = {1, 2, 3, 4, 5}; * * return a; * } * * int* return_integer_array_using_dynamic_allocation(int* result_count) { * *result_count = 5; * * int *a = malloc(5 * sizeof(int)); * * for (int i = 0; i < 5; i++) { * *(a + i) = i + 1; * } * * return a; * } * */ int* getMax(int operations_count, char** operations, int* result_count) { Stack *s = malloc(sizeof(Stack)); s->size = operations_count + 1; s->top = -1; s->arr = malloc(s->size * sizeof(int)); int *a = malloc(*result_count * sizeof(int)); char *input; int cnt = 0; for (int i = 0; i < operations_count; i++) { input = operations[i]; int n = strlen(input); if (n > 1) { char qt[2]; strncpy(qt, input, 1); qt[1] = '\0'; int query_type = atoi(qt); if (query_type == 1) { char *ptr; char element[10]; int j = 0; ptr = input; ptr++; while (*ptr != '\0') { if (strcmp(ptr, " ") == 0) ptr++; else { element[j++] = *ptr; ptr++; } } element[j] = '\0'; int value = atoi(element); push(s, value); } } else { char qt[2]; strncpy(qt, input, 1); qt[1] = '\0'; int query_type = atoi(qt); if (query_type == 2) { pop(s); } else if (query_type == 3) { a[cnt] = maximum(s); cnt++; } } } *result_count = cnt; return a; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); int n = parse_int(ltrim(rtrim(readline()))); char** ops = malloc(n * sizeof(char*)); for (int i = 0; i < n; i++) { char* ops_item = readline(); *(ops + i) = ops_item; } int res_count; int* res = getMax(n, ops, &res_count); for (int i = 0; i < res_count; i++) { fprintf(fptr, "%d", *(res + i)); if (i != res_count - 1) { fprintf(fptr, "\n"); } } fprintf(fptr, "\n"); fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } alloc_length <<= 1; data = realloc(data, alloc_length); if (!data) { data = '\0'; break; } } if (data[data_length - 1] == '\n') { data[data_length - 1] = '\0'; data = realloc(data, data_length); if (!data) { data = '\0'; } } else { data = realloc(data, data_length + 1); if (!data) { data = '\0'; } else { data[data_length] = '\0'; } } return data; } char* ltrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } while (*str != '\0' && isspace(*str)) { str++; } return str; } char* rtrim(char* str) { if (!str) { return '\0'; } if (!*str) { return str; } char* end = str + strlen(str) - 1; while (end >= str && isspace(*end)) { end--; } *(end + 1) = '\0'; return str; } int parse_int(char* str) { char* endptr; int value = strtol(str, &endptr, 10); if (endptr == str || *endptr != '\0') { exit(EXIT_FAILURE); } return value; }
+ 0 comments C++ solution
vector<int> getMax(vector<string> operations) { int a = 0; stack<int> mem; stack<int> max; vector<int> res; for(auto i : operations){ if(i.size() > 1){ a = stoi(i.substr(2)); mem.push(a); if(max.empty() || max.top() <= a){ max.push(a); } } else{ if(i == "2"){ if(mem.top() == max.top()) max.pop(); mem.pop(); } if(i == "3"){ res.push_back(max.top()); } } } return res; }
+ 0 comments I pass only 2 test cases out of 28. What is wrong?
pushed_elements = [] operation_tuples = [tuple(operations[i].split()) for i in range(len(operations))] for o in operation_tuples: if o[0] == '1': pushed_elements.append(int(o[1])) elif o[0] == '2': reversed_pushed_el = pushed_elements[::-1] el_to_remove = reversed_pushed_el[0] pushed_elements.remove(el_to_remove) else: max(pushed_elements)
+ 0 comments My code gave me "Time Limit Exceeded", so anyone can help? https://ideone.com/MN1ybC
+ 1 comment sol by python 3:
def getMax(operations): answer=[] arr=[] max_value=[-math.inf] for oper in operations: now_operation=oper.split() if now_operation[0]=='1': new_value=int(now_operation[1]) arr.append(new_value) max_value.append(max(max_value[-1], new_value)) elif now_operation[0]=='2': arr.pop(-1) max_value.pop(-1) else: answer.append(max_value[-1]) return answer
Load more conversations
Sort 1439 Discussions, By:
Please Login in order to post a comment