12 minutes

# Tracking Maximum Values with Stack Operations

In programming, handling a series of operations on a data structure efficiently is crucial for performance-critical applications. One common problem is efficiently tracking the maximum value in a stack. The provided Python function, `getMax`

, addresses this problem by implementing an algorithm that supports three types of operations: pushing values onto the stack, popping values from the stack, and retrieving the current maximum value in the stack. This article will explain how this function works and the problem it solves.

### The Problem

The primary challenge is to efficiently support the following operations on a stack:

**Push an integer onto the stack.****Pop the integer from the stack.****Retrieve the maximum integer in the stack.**

While a regular stack can efficiently support push and pop operations, retrieving the maximum value would typically require iterating through the stack, leading to an O(n) complexity for each maximum retrieval operation. The `getMax`

function solves this problem by using an auxiliary stack to keep track of the maximum values, thus ensuring that all operations (push, pop, and get maximum) can be performed in constant time, O(1).

### The Solution: `getMax`

Function

Here is the implementation of the `getMax`

function:

```
def getMax(operations):
stack = []
max_stack = [] # Track maximums separately
maxs = []
for i in range(len(operations)):
n = operations[i].split()
if n[0] == '1':
value = int(n[1]) if len(n) == 2 else 0
stack.append(value)
if not max_stack or value >= max_stack[-1]: # Update max_stack
max_stack.append(value)
elif n[0] == '2':
if stack:
popped_value = stack.pop()
if popped_value == max_stack[-1]: # If popped value was the max
max_stack.pop()
elif n[0] == '3':
if stack:
maxs.append(max_stack[-1]) # Directly access the maximum
else:
maxs.append(0)
return maxs
```

### How It Works

**Initialization:**`stack`

is the primary stack used for standard push and pop operations.`max_stack`

is an auxiliary stack that keeps track of the maximum values.`maxs`

is a list to store the results of the maximum value retrieval operations.

**Processing Operations:**- For each operation in the input list
`operations`

, the function splits the operation string to determine the type of operation and any associated value.

- For each operation in the input list
**Push Operation (**`1 x`

):- When the operation is
`1 x`

, the value`x`

is pushed onto the main`stack`

. - The function then checks if
`max_stack`

is empty or if the new value`x`

is greater than or equal to the current maximum value in`max_stack`

. If so,`x`

is also pushed onto`max_stack`

.

- When the operation is
**Pop Operation (**`2`

):- When the operation is
`2`

, the function pops the top value from the main`stack`

. - If the popped value is equal to the top value in
`max_stack`

, it indicates that the maximum value is being removed, so the top value is also popped from`max_stack`

.

- When the operation is
**Get Maximum Operation (**`3`

):- When the operation is
`3`

, the function appends the top value of`max_stack`

(which is the current maximum value in the stack) to the`maxs`

list. - If the stack is empty, it appends 0 to
`maxs`

.

- When the operation is
**Return Results:**- Finally, the function returns the
`maxs`

list, which contains the results of all`3`

operations.

- Finally, the function returns the

### Example Usage

Consider the following input operations:

```
operations = ["1 5", "1 10", "3", "2", "3"]
```

`1 5`

: Push 5 onto the stack. The stack becomes`[5]`

, and`max_stack`

becomes`[5]`

.`1 10`

: Push 10 onto the stack. The stack becomes`[5, 10]`

, and`max_stack`

becomes`[5, 10]`

.`3`

: Retrieve the maximum value. The current maximum is`10`

.`2`

: Pop the top value from the stack. The stack becomes`[5]`

, and`max_stack`

becomes`[5]`

.`3`

: Retrieve the maximum value. The current maximum is`5`

.

The function will return `[10, 5]`

.

### Understanding `if`

, `elif`

, and `else`

in Python

In Python, `if`

, `elif`

, and `else`

are used for conditional statements, allowing the program to execute certain blocks of code based on whether specified conditions are true or false. These keywords form the basis of decision-making in Python programs.

`if`

Statement

The `if`

statement is used to test a condition. If the condition is true, the block of code within the `if`

statement is executed. If the condition is false, the block is skipped.

**Syntax:**

```
if condition:
# Code to execute if condition is true
```

**Example:**

```
x = 10
if x > 5:
print("x is greater than 5")
```

In this example, since `x`

is greater than 5, the message “x is greater than 5” will be printed.

`elif`

Statement

The `elif`

(short for “else if”) statement allows you to check multiple conditions. If the first `if`

condition is false, the program checks the next `elif`

condition. You can have multiple `elif`

statements in your code.

**Syntax:**

```
if condition1:
# Code to execute if condition1 is true
elif condition2:
# Code to execute if condition2 is true
elif condition3:
# Code to execute if condition3 is true
```

**Example:**

```
x = 10
if x > 15:
print("x is greater than 15")
elif x > 5:
print("x is greater than 5 but less than or equal to 15")
```

In this example, since `x`

is not greater than 15 but is greater than 5, the message “x is greater than 5 but less than or equal to 15” will be printed.

`else`

Statement

The `else`

statement catches anything which isn’t caught by the preceding `if`

and `elif`

statements. It’s like a default case when all previous conditions are false.

**Syntax:**

```
if condition1:
# Code to execute if condition1 is true
elif condition2:
# Code to execute if condition2 is true
else:
# Code to execute if none of the above conditions are true
```

**Example:**

```
x = 2
if x > 15:
print("x is greater than 15")
elif x > 5:
print("x is greater than 5 but less than or equal to 15")
else:
print("x is 5 or less")
```

In this example, since `x`

is not greater than 15 and not greater than 5, the message “x is 5 or less” will be printed.

### Application in the `getMax`

Function

Let’s revisit the `getMax`

function and see how `if`

, `elif`

, and `else`

are used:

```
def getMax(operations):
stack = []
max_stack = []
maxs = []
for i in range(len(operations)):
n = operations[i].split()
if n[0] == '1': # Check if the operation is '1 x' (push operation)
value = int(n[1]) if len(n) == 2 else 0
stack.append(value)
if not max_stack or value >= max_stack[-1]: # Update max_stack if necessary
max_stack.append(value)
elif n[0] == '2': # Check if the operation is '2' (pop operation)
if stack:
popped_value = stack.pop()
if popped_value == max_stack[-1]: # If the popped value is the max, update max_stack
max_stack.pop()
elif n[0] == '3': # Check if the operation is '3' (get max operation)
if stack:
maxs.append(max_stack[-1]) # Retrieve the current maximum
else:
maxs.append(0)
return maxs
```

`if n[0] == '1':`

- This condition checks if the current operation is a push operation (
`1 x`

). - If true, it pushes the value onto the stack and updates the
`max_stack`

if the new value is greater than or equal to the current maximum.

- This condition checks if the current operation is a push operation (
`elif n[0] == '2':`

- This condition checks if the current operation is a pop operation (
`2`

). - If true, it pops the value from the stack and, if the popped value is the current maximum, it also pops from the
`max_stack`

.

- This condition checks if the current operation is a pop operation (
`elif n[0] == '3':`

- This condition checks if the current operation is a get max operation (
`3`

). - If true, it appends the current maximum from the
`max_stack`

to the`maxs`

list.

- This condition checks if the current operation is a get max operation (

By using `if`

, `elif`

, and `else`

statements, the `getMax`

function can handle different operations and ensure that the maximum value is tracked efficiently.

The line `value = int(n[1]) if len(n) == 2 else 0`

is a conditional (ternary) expression in Python. It is used to assign a value to the variable `value`

based on a condition. Let’s break down this line in detail:

### Components of the Line

**Condition:**`len(n) == 2`

- This part checks if the length of the list
`n`

is 2. The list`n`

is created by splitting a string operation from the`operations`

list. If the length of`n`

is 2, it means the operation includes a value (e.g.,`['1', '10']`

for the push operation`1 10`

).

- This part checks if the length of the list
**True Case:**`int(n[1])`

- If the condition
`len(n) == 2`

is true, the expression`int(n[1])`

is executed. This converts the second element of the list`n`

(which is a string) to an integer. For example, if`n`

is`['1', '10']`

, then`n[1]`

is`'10'`

, and`int(n[1])`

converts it to`10`

.

- If the condition
**False Case:**`0`

- If the condition
`len(n) != 2`

(i.e., it is false), the expression after`else`

is executed, which is`0`

. This means that if the list`n`

does not have exactly 2 elements, the`value`

will be set to`0`

.

- If the condition

### Complete Ternary Expression

The complete ternary expression is:

```
value = int(n[1]) if len(n) == 2 else 0
```

This can be read as:

- “Assign to
`value`

the integer conversion of`n[1]`

if`n`

has exactly 2 elements; otherwise, assign`0`

to`value`

.”

### Context in the `getMax`

Function

In the context of the `getMax`

function, this line is used to handle the `1 x`

operation, which pushes a value `x`

onto the stack.

```
def getMax(operations):
stack = []
max_stack = []
maxs = []
for i in range(len(operations)):
n = operations[i].split()
if n[0] == '1': # Check if the operation is '1 x' (push operation)
value = int(n[1]) if len(n) == 2 else 0
stack.append(value)
if not max_stack or value >= max_stack[-1]:
max_stack.append(value)
elif n[0] == '2':
if stack:
popped_value = stack.pop()
if popped_value == max_stack[-1]:
max_stack.pop()
elif n[0] == '3':
if stack:
maxs.append(max_stack[-1])
else:
maxs.append(0)
return maxs
```

### Example

Let’s illustrate with an example:

**Input Operation:**`"1 10"`

- When the operation is
`"1 10"`

, splitting this string results in`n = ['1', '10']`

. - The length of
`n`

is 2 (`len(n) == 2`

), so the condition is true. - Therefore,
`value = int(n[1])`

is executed, which means`value = int('10')`

and`value`

is assigned the value`10`

.

- When the operation is
**Input Operation:**`"1"`

- When the operation is
`"1"`

, splitting this string results in`n = ['1']`

. - The length of
`n`

is 1 (`len(n) != 2`

), so the condition is false. - Therefore,
`value = 0`

is executed, and`value`

is assigned the value`0`

.

- When the operation is

This conditional expression ensures that the `value`

is correctly assigned based on the presence or absence of the second element in the operation string, thereby handling both valid push operations (`1 x`

) and invalid ones gracefully.

The line `if not max_stack or value >= max_stack[-1]:`

is a conditional statement used to determine whether to update the `max_stack`

. This line ensures that the current value is added to the `max_stack`

if it is the maximum value so far. Let’s break it down in detail:

### Components of the Line

:`if not max_stack`

- This checks if
`max_stack`

is empty. The`not`

operator returns`True`

if`max_stack`

is empty. If`max_stack`

is empty, it means there is no maximum value recorded yet, so the current value should be added to`max_stack`

.

- This checks if
:`or`

- This is a logical operator that connects two conditions. If either of the conditions (on its left or right) is
`True`

, the whole expression evaluates to`True`

.

- This is a logical operator that connects two conditions. If either of the conditions (on its left or right) is
:`value >= max_stack[-1]`

- This checks if the current
`value`

is greater than or equal to the last element in`max_stack`

(`max_stack[-1]`

). The`-1`

index refers to the last element in the list. `max_stack`

is used to keep track of the maximum values in the stack. The last element of`max_stack`

is always the current maximum value of the main stack.- If
`value`

is greater than or equal to the current maximum (`max_stack[-1]`

), then`value`

should be added to`max_stack`

because it is the new maximum.

- This checks if the current

### Putting It All Together

The entire conditional statement:

```
if not max_stack or value >= max_stack[-1]:
```

This can be interpreted as:

- “If
`max_stack`

is empty (no maximum value recorded yet), or the current`value`

is greater than or equal to the current maximum value in`max_stack`

, then execute the following block of code.”

### Context in the `getMax`

Function

In the `getMax`

function, this line is used to update `max_stack`

when a new value is pushed onto the main `stack`

:

```
def getMax(operations):
stack = []
max_stack = []
maxs = []
for i in range(len(operations)):
n = operations[i].split()
if n[0] == '1': # Check if the operation is '1 x' (push operation)
value = int(n[1]) if len(n) == 2 else 0
stack.append(value)
if not max_stack or value >= max_stack[-1]:
max_stack.append(value)
elif n[0] == '2':
if stack:
popped_value = stack.pop()
if popped_value == max_stack[-1]:
max_stack.pop()
elif n[0] == '3':
if stack:
maxs.append(max_stack[-1])
else:
maxs.append(0)
return maxs
```

### Example

Let’s illustrate this with an example:

**First Push Operation:**`1 5`

`value = 5`

`stack`

becomes`[5]`

- Since
`max_stack`

is empty,`not max_stack`

is`True`

. `value (5)`

is added to`max_stack`

, so`max_stack`

becomes`[5]`

.

**Second Push Operation:**`1 10`

`value = 10`

`stack`

becomes`[5, 10]`

`max_stack`

is not empty, so`not max_stack`

is`False`

.- Check
`value (10) >= max_stack[-1] (5)`

, which is`True`

. `value (10)`

is added to`max_stack`

, so`max_stack`

becomes`[5, 10]`

.

**Third Push Operation:**`1 7`

`value = 7`

`stack`

becomes`[5, 10, 7]`

`max_stack`

is not empty, so`not max_stack`

is`False`

.- Check
`value (7) >= max_stack[-1] (10)`

, which is`False`

. `value (7)`

is not added to`max_stack`

, so`max_stack`

remains`[5, 10]`

.

By using this condition, the function ensures that `max_stack`

always contains the maximum values in order, making it efficient to retrieve the current maximum value when needed.

### Conclusion

The `getMax`

function efficiently handles the problem of tracking the maximum value in a stack with constant time complexity for all operations. By using an auxiliary stack (`max_stack`

), it ensures that the maximum value can always be accessed quickly, making it an ideal solution for scenarios where frequent maximum value retrievals are required.

Here’s another problem for you to solve using `if`

, `elif`

, and `else`

statements:

### Problem: Leap Year Checker

Write a Python function that takes a year as input and determines whether it is a leap year. The function should return `True`

if the year is a leap year and `False`

otherwise. A year is a leap year if:

- It is divisible by 4, and
- It is not divisible by 100, unless
- It is also divisible by 400.

### Example

`is_leap_year(2020)`

should return`True`

`is_leap_year(1900)`

should return`False`

`is_leap_year(2000)`

should return`True`

### Hint

You’ll need to use `if`

, `elif`

, and `else`

to check the various conditions for determining if a year is a leap year. Good luck!