data_structures.stacks.next_greater_element

Attributes

arr
expect
setup

Functions

next_greatest_element(→ list[float])	Efficient solution to find the Next Greatest Element (NGE) for all elements
next_greatest_element_fast(→ list[float])	Find the Next Greatest Element (NGE) for each element in the array
next_greatest_element_slow(→ list[float])	Get the Next Greatest Element (NGE) for each element in the array

Module Contents

data_structures.stacks.next_greater_element.next_greatest_element(arr: list[float]) → list[float]

Efficient solution to find the Next Greatest Element (NGE) for all elements using a stack. The time complexity is reduced to O(n), making it suitable for larger arrays.

The stack keeps track of elements for which the next greater element hasn’t been found yet. By iterating through the array in reverse (from the last element to the first), the stack is used to efficiently determine the next greatest element for each element.

Args:

arr: List of numbers for which the NGE is calculated.

Returns:

List containing the next greatest elements. If no greater element is found, -1 is placed in the result.

Example: >>> next_greatest_element(arr) == expect True

data_structures.stacks.next_greater_element.next_greatest_element_fast(arr: list[float]) → list[float]

Find the Next Greatest Element (NGE) for each element in the array using a more readable approach. This implementation utilizes enumerate() for the outer loop and slicing for the inner loop.

While this improves readability over next_greatest_element_slow(), it still has a time complexity of O(n^2).

Args:

arr: List of numbers for which the NGE is calculated.

Returns:

List containing the next greatest elements. If no greater element is found, -1 is placed in the result.

Example: >>> next_greatest_element_fast(arr) == expect True

data_structures.stacks.next_greater_element.next_greatest_element_slow(arr: list[float]) → list[float]

Get the Next Greatest Element (NGE) for each element in the array by checking all subsequent elements to find the next greater one.

This is a brute-force implementation, and it has a time complexity of O(n^2), where n is the size of the array.

Args:

arr: List of numbers for which the NGE is calculated.

Returns:

List containing the next greatest elements. If no greater element is found, -1 is placed in the result.

Example: >>> next_greatest_element_slow(arr) == expect True

data_structures.stacks.next_greater_element.arr

data_structures.stacks.next_greater_element.expect

data_structures.stacks.next_greater_element.setup = 'from __main__ import arr, next_greatest_element_slow, next_greatest_element_fast, next_greatest_element'