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:

  1. Push an integer onto the stack.
  2. Pop the integer from the stack.
  3. 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Return Results:

    • Finally, the function returns the maxs list, which contains the results of all 3 operations.

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

  1. 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.

  2. 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.

  3. 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.

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

  1. 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).

  2. 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.

  3. 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.

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:

  1. 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.

  2. 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.

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

  1. 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.

  2. 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.

  3. 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.

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:

  1. 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].

  2. 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].

  3. 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:

  1. It is divisible by 4, and
  2. It is not divisible by 100, unless
  3. 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!