data_structures.stacks.kth_next_greater_element
===============================================

.. py:module:: data_structures.stacks.kth_next_greater_element

.. autoapi-nested-parse::

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



Attributes
----------

.. autoapisummary::

   data_structures.stacks.kth_next_greater_element.expected_answers
   data_structures.stacks.kth_next_greater_element.setup
   data_structures.stacks.kth_next_greater_element.test_array
   data_structures.stacks.kth_next_greater_element.test_k


Functions
---------

.. autoapisummary::

   data_structures.stacks.kth_next_greater_element.find_kth_next_greater_element


Module Contents
---------------

.. py:function:: 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


.. py:data:: expected_answers

.. py:data:: setup
   :value: 'from __main__ import test_array, test_k, find_kth_next_greater_element'


.. py:data:: test_array

.. py:data:: test_k
   :value: 10