Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NextGreaterElementIndex

Source Notebook

For each element of a list, find the index of the next greater element

Contributed by: Shenghui Yang

ResourceFunction["NextGreaterElementIndex"][list]

for each element of list, find the index of the next numerically greater element.

ResourceFunction["NextGreaterElementIndex"][list,p]

find the indices using order function p.

Details

The single argument input must be a list of real valued numeric values.
The ordering function p can be NumericalOrder, LexicographicOrder, AlphabeticOrder and Order.
The ordering function p applies to a pair of elements following the description on the OrderedQ function page
If there is no element to the right that is greater than the current item, the function returns -1 for the index.
The function uses a monotonic stack to keep track of the indices of visited items. If a new value is larger than the item at the top of the current stack, one pops the stack and updates the solution with the difference between the index of this value and the popped value. Repeat until the stack is empty.
The complexity of the algorithm is O(n) because each item is used at most once in the stack and the outer loop only moves forward. The brute force method is O(n2).

Examples

Basic Examples (3) 

Visualize the input data:

In[1]:=
data = {-2, 3, 4, 1, 6, 2, 1, 3}; ListLinePlot[Callout /@ data, Ticks -> {Range[8], None}]
Out[2]=

The indices of the next greater elements:

In[3]:=
indices = ResourceFunction["NextGreaterElementIndex"][data]
Out[3]=

Except for columns ending in -1, each second item is the next greater element:

In[4]:=
Grid[{data, data[[indices]], indices}, Frame -> All]
Out[4]=

Scope (2) 

For non-numeric input, one may use customized order function:

In[5]:=
SeedRandom["Dates"]; dates = RandomDate[{DateObject[{2025, 1}, "Month"], DateObject[{2025, 12}, "Month"]}, 10]
Out[6]=

For instance the sixth item in the date list, , is the next later day than :

In[7]:=
ResourceFunction["NextGreaterElementIndex"][dates, NumericalOrder]
Out[7]=

Comparable Quantity objects are supported:

In[8]:=
SeedRandom["10Units"]; data = MapThread[Quantity[#1, #2] &, { RandomReal[{1, 5}, 10], RandomChoice[{"Feet", "Meters", "Kilometers", "Millimeters", "Inches"}, 10]}];
In[9]:=
ResourceFunction["NextGreaterElementIndex"][data, NumericalOrder]
Out[9]=

Check the index of each next greater item visually:

In[10]:=
ListLogPlot[QuantityMagnitude[UnitConvert[#, "Meters"] & /@ data], Joined -> True]
Out[10]=

Applications (3) 

Collect and show data for a stock:

In[11]:=
fd = FinancialData["MSFT", {{2024, 8, 1}, {2024, 10, 1}}];
In[12]:=
DateListPlot[fd]
Out[12]=

Find the wait time to observe an overshoot in stock price for a given duration:

In[13]:=
dp = fd["DatePath"]; idx = ResourceFunction["NextGreaterElementIndex"][dp, NumericalOrder[#1[[2]], #2[[2]]] &]
Out[14]=

Tabulate the current price and next high:

In[15]:=
ResourceFunction[ ResourceObject[<|"Name" -> "NiceGrid", "ShortName" -> "NiceGrid", "UUID" -> "d46856e8-5702-4b8b-addf-d92743399b5f", "ResourceType" -> "Function", "Version" -> "2.0.0", "Description" -> "Nicely format data in various structures into a grid format", "RepositoryLocation" -> URL[ "https://www.wolframcloud.com/obj/resourcesystem/api/1.0"], "SymbolName" -> "FunctionRepository`$8d6838630917472ab156bd9f4b91491e`NiceGrid", "FunctionLocation" -> CloudObject[ "https://www.wolframcloud.com/obj/22e777c3-ca4a-4e8b-a448-bbf28aa4ef3a"]|>, ResourceSystemBase -> Automatic]][MapThread[ {If[# == -1, "Never", QuantityMagnitude@ DateDifference[dp[[#2, 1]], dp[[#1, 1]]]], #3} &, {idx, Range[Length[idx]], fd["Values"]} ], { "Next Higher price after # day(s)", "Price"}, "MaxNumber" -> 20]
Out[15]=

Possible Issues (4) 

An empty input list returns an empty list:

In[16]:=
ResourceFunction["NextGreaterElementIndex"][{}]
Out[16]=

A single element list returns {-1}:

In[17]:=
ResourceFunction["NextGreaterElementIndex"][{1231}]
Out[17]=

The single argument input must be a list of real valued numeric values. Otherwise the function returns unevaluated:

In[18]:=
{ResourceFunction["NextGreaterElementIndex"][{1, 2, x}], ResourceFunction["NextGreaterElementIndex"][{{1, 2}}]}
Out[18]=

For non-comparable items, Order is applied automatically:

In[19]:=
ResourceFunction[ "NextGreaterElementIndex"][{Quantity[1, "Meters"], Quantity[1, "Kelvins"]}, Order]
Out[19]=
In[20]:=
ResourceFunction[ "NextGreaterElementIndex"][{Quantity[1, "Meters"], Quantity[1, "Kelvins"]}, NumericalOrder]
Out[20]=

Publisher

Shenghui Yang

Requirements

Wolfram Language 14.0 (January 2024) or above

Version History

  • 1.0.0 – 03 February 2025

Source Metadata

  • Citation:
    • T. H. Cormen, C. E. Leiserson and R. L. Rivest, "Introduction to Algorithms", ISBN: 9780262530910

Related Resources

Author Notes

If inputs are all integer, we can compile the function to have hundreds time speed booster:

In[1]:=
cf = FunctionCompile[ Function[Typed[arg, "PackedArray"::["MachineInteger", 1]], Module[{ds, gap, enum, idx, len}, len = Length[arg]; ds = TypeHint[CreateDataStructure["Stack"], "Stack"::["MachineInteger"]]; gap = ConstantArray[0, len]; enum = Range[len]; Do[ While[! ds["EmptyQ"] && arg[[item]] > arg[[ds["Peek"]]], idx = ds["Pop"]; gap[[idx]] = item - idx ]; ds["Push", item] , {item, len}]; MapThread[If[#1 == 0, -1, #2 + #1] &, {gap, Range[len]}] ]]]

Less than half sec for 10M input values:

In[2]:=
test = cf[RandomInteger[{-1000, 1000}, 10000000]]; // AbsoluteTiming

License Information