Next Greater Element

Data Structures and Algorithms

Statement

Given two distinct integer arrays n1 and n2, where n1 is a subset of n2, find all the next greater elements for n1 in the corresponding places of n2.

In general, the next greater element of an element x in an array is the first greater element present on the right side of x in the same array. However, in the context of this problem, for each element x in n1, find the next greater element present on the right side of x in n2 and store it in an answer array. If there’s no such element, store -1 for this number.

Return the answer array after finding the next greater elements.

Constraints

• 1 ≤ n1.length() ≤ n2.length() ≤ 10³
• 0 ≤ n1[i], n2[i] ≤ 10⁴
• n1 has distinct integers
• n2 has distinct integers
• All integers in n1 also appear in n2

Solution

"""
production algorithm
"""

from data_structures.stack.stack import Stack


class Solution:
    def next_greater_element(self, n1, n2):
        """
        time complexity O(n)
        space complexity O(n)
        """
        stack, hashmap = Stack(), dict()
        stack.push(n2[0])
        hashmap[n2[0]] = -1

        for i in range(1, len(n2)):
            while not stack.empty() and stack.top() < n2[i]:
                number = stack.pop()
                hashmap[number] = n2[i]
            stack.push(n2[i])
            hashmap[n2[i]] = -1

        result = [hashmap[n1[i]] for i in range(len(n1))]
        return result

"""
unit tests
"""

from unittest import TestCase
from algorithms.hashmaps.next_greater_element.solution import Solution


class SolutionTestCase(TestCase):
    def test_zero_next_greater_elements(self):
        # Given
        n2 = [15, 13, 11, 9, 7, 5, 3, 1]
        n1 = [15, 11, 7, 3]
        solution = Solution()

        # When
        actual = solution.next_greater_element(n1, n2)

        # Then
        expected = [-1, -1, -1, -1]
        self.assertEqual(actual, expected)

    def test_some_next_greater_elements(self):
        # Given
        n2 = [0, 4, -6, -13, 15, -8, -15, 5, 20, -10, 12, 10]
        n1 = [4, -13, -8, 5, -10, 10]
        solution = Solution()

        # When
        actual = solution.next_greater_element(n1, n2)

        # Then
        expected = [15, 15, 5, 20, 12, -1]
        self.assertEqual(actual, expected)

    def test_all_next_greater_elements(self):
        # Given
        n2 = [1, 3, 5, 7, 9, 11, 13, 15]
        n1 = [1, 5, 9, 13]
        solution = Solution()

        # When
        actual = solution.next_greater_element(n1, n2)

        # Then
        expected = [3, 7, 11, 15]
        self.assertEqual(actual, expected)

Strategy

Hash Maps.

Explanation

The algorithm uses a stack and a hash map. The stack is used to hold previous elements which don’t have a next greater element found yet. In contrast, the hash map is used to hold elements which have a next greater element found. At the start, the stack is initialized with the first element of n2, and its value in the hash map is initialized to -1.

Then, the values of n2 are iterated. For each element of n2, if it’s greater than the top of the stack, then the next greater element on the right side of that element on top of the stack has been found. Repeat while the stack has elements and the top of the stack is less than the current element of iteration. At the end of each iteration, without condition, push the current element of iteration to the stack, and set its value in the hash map to -1.

After iteration with the elements of n2, iterate with the elements of n1. Since n1 is a subset of n2, each element of n1 will have a key-value pair in the hash map. Create a result array of the next greater element of each element of n1. Then, return the result array.

Time Complexity

At most, every element of n2 is visited twice with takes linear time. Therefore, the time complexity of the algorithm is O(n), where n is the length of n2.

Space Complexity

The dictionary grows to size n, and at worst the stack grows to size n, which is linear auxiliary space. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/hashmaps/next_greater_element at main ·…