data_structures.stacks.kth_next_greater_element

Implement the function to find kth Next Greatest Element (NGE) for all elements.

Attributes

expected_answers
setup
test_array
test_k

Functions

find_kth_next_greater_element(→ list[int | float | None])

Efficient general method to seek the kth NGE for all elements.

Module Contents

data_structures.stacks.kth_next_greater_element.find_kth_next_greater_element(array: list[int | float], kth_ord: int) → list[int | float | None]

Efficient general method to seek the kth NGE for all elements. Approach is entirely based on k stacks, which are actually very easy to understand. These k stacks symbolize how many NGEs an element has already found.

For example, for 1 <= j <= k, if an element is currently at the jth stack, it means that this element has found its (j - 1)th NGE, now looking for jth NGE.

By processing stacks from higher to lower ordinals, we can always ensure that each stack stays monotonically non-increasing in terms of element value.

Time complexity: O(kn) where n is the length of input array. However, if k >= n, all elements won’t find their respective kth NGE. As a result, worst case time complexity is O(n^2) when k < n but k ≈ n.

Space complexity: O(n), since at any point, an element is only in one of k stacks.

Args:

array (list[int | float]): A list for which the kth NGE is computed.

A mix of integers and floats in list is allowed.

kth_ord (int): Ordinal of the NGE to find. kth_ord must be a positive integer.

Returns:

A list containing each element’s kth NGE. If an element can’t find its kth NGE, None, instead of -1, is put as its entry, because input array might have -1.

Example: >>> find_kth_next_greater_element([1, 2, 3, 4, 5], 3) == [4, 5, None, None, None] True >>> find_kth_next_greater_element([2.5, 1.9, 4.3, 6.0], 1) == [4.3, 4.3, 6.0, None] True >>> find_kth_next_greater_element([1, 2, 3], 0) Traceback (most recent call last):

…

ValueError: kth_ord must be a positive integer. >>> find_kth_next_greater_element(list(range(1000)), 1000) == [None] * 1000 True >>> find_kth_next_greater_element(test_array, test_k) == expected_answers True

data_structures.stacks.kth_next_greater_element.expected_answers

data_structures.stacks.kth_next_greater_element.setup = 'from __main__ import test_array, test_k, find_kth_next_greater_element'

data_structures.stacks.kth_next_greater_element.test_array

data_structures.stacks.kth_next_greater_element.test_k = 10