Designing a New DATA STRUCTURE for a Coding Interview! | Min Stack - Leetcode 155

leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[simonharris]

You don't need to push a -1 for the 5. You only need to push to the min-stack when the minimum changes or repeats. When you pop the 5, it's different from the top of the min-stack, so do not pop from the min-stack. When you pop the -1, it's the same as the top of the min-stack, so DO pop from the min-stack. You would also need to push to the min-stack if you were to push another -1. This would reduce the size of the min-stack considerably.

[DavideCanton]

Now implement it in rust, but as a generic version, not a soecific one on integers

[NikSoparis]

No chance you can do away with that seemingly loop effect right? Otherwise great channel

[TheMachina]

can't you just use a variable that gets updated when pushing ? like you define a struct with

struct stack {
 int capacity;
int count;
int min;
int *data;
}

and when you push you make a comparaison :

void stack_push(struct stack *stack, int value)
{
if (!stack || stack_is_full(stack))
// handle logic
if ( value < stack->min)
stack->min = value;
push->stack[++stack->count] = value;
}
or maybe the min value is always maintained at count + 1 such that poping it doesn't affect the stack behaviour. idk just a second arrray seems like a very wasteful thing to do.

[brycejohansen]

I was wondering if a Min Heap Binary Tree would do the job here.

[IlyesCodes]

That is amazing ... My only concern is memory space it feels like it takes up more memory ... Please correct me if I'm mistaking im new to coding challenges

[warguy]

ill give u this one never woulda thought of this one, weird

[patrickbateman]

Yet another thing you're asked in coding interviews and will never use in the job. How will a project manager react when he finds out an intern is coding a data structure from scratch?