Max Stack - Problem

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object.
void push(int x) Pushes element x onto the stack.
int pop() Removes the element on top of the stack and returns it.
int top() Gets the element on the top of the stack without removing it.
int peekMax() Retrieves the maximum element in the stack without removing it.
int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(log n) for each other call.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MaxStack","push","push","top","popMax","top"], values = [[],[5],[1],[],[],[]]

› Output: [null,null,null,1,5,1]

💡 Note: MaxStack() creates empty stack. push(5) adds 5. push(1) adds 1 on top. top() returns 1 (top element). popMax() removes and returns 5 (maximum). top() returns 1 (now the only element).

Example 2 — Multiple Max Elements

$ Input: operations = ["MaxStack","push","push","push","peekMax","popMax","top"], values = [[],[5],[1],[5],[],[],[]]

› Output: [null,null,null,null,5,5,1]

💡 Note: After pushing 5,1,5: stack is [5,1,5]. peekMax() returns 5. popMax() removes the top-most 5, leaving [5,1]. top() returns 1.

Example 3 — Pop vs PopMax

$ Input: operations = ["MaxStack","push","push","push","pop","popMax"], values = [[],[3],[2],[1],[],[]]

› Output: [null,null,null,null,1,3]

💡 Note: Stack becomes [3,2,1]. pop() removes top element 1, leaving [3,2]. popMax() removes maximum 3, leaving [2].

Constraints

-10⁷ ≤ x ≤ 10⁷
At most 10⁵ calls will be made to push, pop, top, peekMax, and popMax.
There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Visualization

Tap to expand

Asked in

G Google 45 A Amazon 38 F Facebook 32 M Microsoft 28

The key insight is to combine a doubly-linked list for stack operations with an ordered data structure (TreeMap/OrderedDict) for efficient max operations. The doubly-linked list provides O(1) access to the top element, while the ordered structure enables O(log n) max operations. Best approach uses Doubly-Linked List + TreeMap. Time: O(1) for top, O(log n) for others, Space: O(n)

Common Approaches

✓ Greedy

⏱️ Time: N/A Space: N/A

Array with Linear Search

⏱️ Time: O(n) Space: O(n)

Store elements in an array and maintain stack operations. For max operations, search through the entire array to find maximum element.

Doubly Linked List + Ordered Set

⏱️ Time: O(log n) Space: O(n)

Maintain elements in a doubly-linked list for stack operations and use an ordered set to track elements by value for efficient max operations. Each node has pointers to maintain both structures.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 100000

static int stack[MAX_SIZE][2];  // [value, id]
static int stack_size = 0;
static int max_map_data[MAX_SIZE];  // all IDs stored sequentially
static int max_map_start[MAX_SIZE * 2 + 1];  // start index for each value
static int max_map_sizes[MAX_SIZE * 2 + 1];  // size for each value
static bool removed[MAX_SIZE];
static int next_id = 0;
static int max_keys[MAX_SIZE];
static int max_keys_size = 0;
static int value_offset = MAX_SIZE;  // offset for negative values
static int data_ptr = 0;

void init_max_stack() {
    stack_size = 0;
    memset(max_map_sizes, 0, sizeof(max_map_sizes));
    memset(max_map_start, 0, sizeof(max_map_start));
    memset(removed, false, sizeof(removed));
    next_id = 0;
    max_keys_size = 0;
    data_ptr = 0;
}

void insert_sorted_int(int arr[], int *size, int val) {
    int pos = 0;
    while (pos < *size && arr[pos] < val) {
        pos++;
    }
    for (int i = *size; i > pos; i--) {
        arr[i] = arr[i-1];
    }
    arr[pos] = val;
    (*size)++;
}

void remove_int(int arr[], int *size, int val) {
    int pos = -1;
    for (int i = 0; i < *size; i++) {
        if (arr[i] == val) {
            pos = i;
            break;
        }
    }
    if (pos >= 0) {
        for (int i = pos; i < *size - 1; i++) {
            arr[i] = arr[i+1];
        }
        (*size)--;
    }
}

bool contains_int(int arr[], int size, int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) return true;
    }
    return false;
}

void insert_id_sorted(int idx, int id) {
    if (max_map_sizes[idx] == 0) {
        max_map_start[idx] = data_ptr;
        max_map_data[data_ptr] = id;
        data_ptr++;
        max_map_sizes[idx] = 1;
        return;
    }
    
    // Find position to insert
    int start = max_map_start[idx];
    int size = max_map_sizes[idx];
    int pos = 0;
    while (pos < size && max_map_data[start + pos] < id) {
        pos++;
    }
    
    // Shift data to make room
    for (int i = data_ptr; i > start + pos; i--) {
        max_map_data[i] = max_map_data[i-1];
    }
    
    // Update all start indices after this one
    for (int i = 0; i < MAX_SIZE * 2 + 1; i++) {
        if (max_map_sizes[i] > 0 && max_map_start[i] > start) {
            max_map_start[i]++;
        }
    }
    
    max_map_data[start + pos] = id;
    max_map_sizes[idx]++;
    data_ptr++;
}

void remove_id(int idx, int id) {
    int start = max_map_start[idx];
    int size = max_map_sizes[idx];
    int pos = -1;
    
    for (int i = 0; i < size; i++) {
        if (max_map_data[start + i] == id) {
            pos = i;
            break;
        }
    }
    
    if (pos >= 0) {
        // Shift data left
        for (int i = start + pos; i < data_ptr - 1; i++) {
            max_map_data[i] = max_map_data[i + 1];
        }
        
        // Update all start indices after this one
        for (int i = 0; i < MAX_SIZE * 2 + 1; i++) {
            if (max_map_sizes[i] > 0 && max_map_start[i] > start) {
                max_map_start[i]--;
            }
        }
        
        max_map_sizes[idx]--;
        data_ptr--;
    }
}

int get_max_id(int idx) {
    if (max_map_sizes[idx] == 0) return -1;
    int start = max_map_start[idx];
    int size = max_map_sizes[idx];
    return max_map_data[start + size - 1];
}

void push(int x) {
    stack[stack_size][0] = x;
    stack[stack_size][1] = next_id;
    stack_size++;
    
    int idx = x + value_offset;
    insert_id_sorted(idx, next_id);
    
    if (!contains_int(max_keys, max_keys_size, x)) {
        insert_sorted_int(max_keys, &max_keys_size, x);
    }
    
    next_id++;
}

int pop() {
    while (stack_size > 0 && removed[stack[stack_size-1][1]]) {
        stack_size--;
    }
    
    stack_size--;
    int val = stack[stack_size][0];
    int id_val = stack[stack_size][1];
    removed[id_val] = true;
    
    int idx = val + value_offset;
    remove_id(idx, id_val);
    
    if (max_map_sizes[idx] == 0) {
        remove_int(max_keys, &max_keys_size, val);
    }
    
    return val;
}

int top() {
    while (stack_size > 0 && removed[stack[stack_size-1][1]]) {
        stack_size--;
    }
    return stack[stack_size-1][0];
}

int peek_max() {
    return max_keys[max_keys_size-1];
}

int pop_max() {
    int max_val = max_keys[max_keys_size-1];
    int idx = max_val + value_offset;
    int max_id = get_max_id(idx);
    
    removed[max_id] = true;
    remove_id(idx, max_id);
    
    if (max_map_sizes[idx] == 0) {
        remove_int(max_keys, &max_keys_size, max_val);
    }
    
    return max_val;
}

void solve_operations(char operations[][20], int values[][10], int op_count, int results[]) {
    for (int i = 0; i < op_count; i++) {
        if (strcmp(operations[i], "MaxStack") == 0) {
            init_max_stack();
            results[i] = -999999;  // null marker
        } else if (strcmp(operations[i], "push") == 0) {
            push(values[i][0]);
            results[i] = -999999;  // null marker
        } else if (strcmp(operations[i], "pop") == 0) {
            results[i] = pop();
        } else if (strcmp(operations[i], "top") == 0) {
            results[i] = top();
        } else if (strcmp(operations[i], "peekMax") == 0) {
            results[i] = peek_max();
        } else if (strcmp(operations[i], "popMax") == 0) {
            results[i] = pop_max();
        }
    }
}

int parse_operations(char* line, char operations[][20]) {
    int count = 0;
    char* ptr = line + 1;  // skip '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '"') {
            ptr++;
            int len = 0;
            while (*ptr && *ptr != '"') {
                operations[count][len++] = *ptr++;
            }
            operations[count][len] = '\0';
            count++;
            if (*ptr) ptr++;  // skip closing quote
        }
        if (*ptr == ',') ptr++;
    }
    return count;
}

int parse_values(char* line, int values[][10]) {
    int count = 0;
    char* ptr = line + 1;  // skip '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int val_count = 0;
            while (*ptr && *ptr != ']') {
                if ((*ptr >= '0' && *ptr <= '9') || *ptr == '-') {
                    values[count][val_count++] = strtol(ptr, &ptr, 10);
                } else {
                    ptr++;
                }
                if (*ptr == ',') ptr++;
            }
            count++;
        }
        if (*ptr) ptr++;
    }
    return count;
}

int main() {
    char line[10000];
    char operations[1000][20];
    int values[1000][10];
    int results[1000];
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    int op_count = parse_operations(line, operations);
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    parse_values(line, values);
    
    solve_operations(operations, values, op_count, results);
    
    printf("[");
    for (int i = 0; i < op_count; i++) {
        if (i > 0) printf(",");
        if (results[i] == -999999) {
            printf("null");
        } else {
            printf("%d", results[i]);
        }
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

89.1K Views

Medium Frequency

~35 min Avg. Time

1.9K Likes

Ln 1, Col 1

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen