Next Greater Problem And Its Homies

“You got a new friend. well. I got homies.” — Heartless by Kanye West

It is very common to see the next greater element problems these days. In this article, I will go from solving the vanilla form of this problem to analyzing and illustrating some of its variants. I will talk about when to sort, how to traverse (from left or right), and when we will need an auxiliary array.

Overview

Vanilla form: Given an array A, for each element at index i, find eligible indexes j such that A[i] < A[j] and i < j
Variant 1: Vanilla form + for all the eligible js of index i, find the j such that A[j] is the largest one
Variant 2: Vanilla form + for all the eligible js of index i, find the j such that A[j] is the smallest one
Variant 3: Vanilla form + for all the eligible js of index i, find the j such that j is the largest
Variant 4: Vanilla form + for all the eligible js of index i, find the j such that j is the smallest
Variant 5: Vanilla form + for all the eligible js of index i, find the largest j such that any element between [i+1, j] is larger than A[i]

Vanilla Form

Problem Statement

Given an array A, for each element at index i, find eligible indexes j such that A[i] < A[j] and i < j.

Examples

Example 1:

A  =  [1,  6,  2,  7,  8,  0]
then    at index 0, A[0] = 1. eligible js are: 1, 2, 3, 4. because A[1] > A[0], A[2] > A[0], A[3] > A[0], A[4] > A[0]. 
                                                        Since A[5] < A[0], index 5 does not qualify. 
        at index 1, A[1] = 6, eligible js are: 3, 4 
        at index 2, A[2] = 2, eligible js are: 3, 4
        at index 3, A[3] = 7, eligible js are: 4 
        at index 4, A[4] = 8, No eligible j 
        at index 5, A[5] = 0, No eligible j 
Hence, res = [[1, 2, 3, 4], [3, 4], [4], [], []]

Example 2:

A = [5, 0, 2, 1, 3, 4]  => res = [[], [2, 3, 4, 5], [4, 5], [4, 5], [5], []]

Brute Force

An obvious way is brute force, for each element i, loop from i+1 to the end of the array, add all the js which satisfies A[j] > A[i]. Time Complexity: O(n²)

def baseForm(A): 
    n = len(A)
    res = [[] for i in range(n)] 
    for i in range(n): 
        for j in range(i+1, n): 
            if A[j] > A[i]: 
                res[i].append(j) 
    return res 

Can we do better than O(n²)? Yes. We can make it O(nlogn). Of course, O(nlogn) didn’t count the time to copy indexes into the result array. There are several ways to achieve this. Since the base form optimization is not the focus of this post, I will create another post for it.

Variant 1

Vanilla form + for all the eligible js of index i, find the j such that A[j] is the largest one.

Problem Statement

Given an array A, for each element at index i, among all the eligible indexes j such that A[i] < A[j] and i < j, find the j such that A[j] is the largest one.

Examples

Example 1:

A       =  [1,  6,  2,  7,  8,  0]
then at index 0, A[0] = 1, among eligible js including: 1, 2, 3, 4.  A[4] > A[3] > A[1] > A[2]
        at index 1, A[1] = 6, among eligible js including: 3, 4, A[4] > A[3]
        at index 2, A[2] = 2, among eligible js including: 3, 4, A[4] > A[3]
        at index 3, A[3] = 7, only one eligible j: 4 
        at index 4, A[4] = 8, No eligible j 
        at index 5, A[5] = 0, No eligible j 
Hence, res = [4, 4, 4, 4, -1, -1]

Example 2:

A = [5, 0, 2, 1, 3, 4]  => res = [-1, 5, 5, 5, 5, -1]

Brute Force: O(n²)

def v1_brute_force(A): 
    n = len(A)
    res = [-1] * n 
    for i in range(n): 
        for j in range(i+1, n): 
            if A[j] > A[i]:
                if res[i] == -1 or A[res[i]] < A[j]: 
                    res[i] = j 
    return res

With Technique: O(n)

This problem is asking for the index of the largest element between [i+1, n-1] for each index i in A. Let’s traverse from right to left and maintain the index of the largest element as maxidx. In this way, at index i, if A[i] > A[maxidx], it means no element in [i+1, n-1] is greater than A[i]. Hence res[i] = -1. A[i] is the largest element between [i, n-1] and maxidx should be updated to i. if A[i] <= A[maxidx], then A[maxidx] is the largest element so far. res[i] = maxidx.

def v1_adv(A):
    n = len(A)
    res = [-1] * n
    maxidx = n-1
    for i in range(n-2, -1, -1):
        if A[maxidx] >= A[i]:
            res[i] = maxidx
        else:
            maxidx = i
    return res

[… continued in next sections …]

Conclusion

At this point, since you have seen the next greater problem and its five homies, you are already very familiar with the next greater patterns. The trick is to decide where to traverse (left or right), when to sort (during traverse or before), how to sort (index increasing or decreasing, value increasing or decreasing), what to store (use a stack or array?).

Here are some problems where you can test your knowledge. They are not exactly the same problem, but hopefully, you can feel how they are bonded when practicing: