python coding test course, finding the next greater number

Hello! Today, we will introduce and explain the algorithm problem ‘Finding Next Greater Element’, which is very useful for job seekers. This problem will greatly help in understanding and utilizing the concept of stacks. So, shall we begin?

Problem Description

Problem Description: This is a problem of finding the “next greater element” for each element in the given array. The “next greater element” refers to the first element that is greater than the current element on its right. If such an element does not exist, it is represented as -1.

Input: The first line contains a natural number N (1 ≤ N ≤ 1,000,000), and the second line contains N natural numbers A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000).

Output: Print the next greater element for each element, one per line.

Example

Input:

5
2 1 3 4 5

Output:

3
3
4
5
-1

Problem Solving Strategy

One of the most effective ways to solve this problem is by using a stack. A stack is a Last In, First Out (LIFO) data structure that can be utilized effectively in solving this problem.

Approach Using a Stack

  1. Create an empty stack.
  2. Traverse the given array from right to left, performing the following for each element:
    1. Compare the current element with the top element of the stack.
    2. If the top element of the stack is greater than the current element, that element is the next greater element. Store the next greater element for the current element.
    3. If the top element of the stack is smaller than or equal to the current element or if the stack is empty, pop elements from the stack.
    4. Add the current element to the stack.
  3. After traversing all elements, print the result array storing the next greater elements.

Code Implementation

Now, let’s implement the above algorithm in Python code.


def find_next_greater_element(arr):
    n = len(arr)
    result = [-1] * n  # Result array to store next greater elements
    stack = []  # Create a stack

    # Traverse the array from right to left
    for i in range(n - 1, -1, -1):
        # Compare with the top element of the stack
        while stack and stack[-1] <= arr[i]:
            stack.pop()  # Pop from the stack
        
        # If the stack is not empty, record the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Add the current element to the stack
        stack.append(arr[i])

    return result

# Input handling
n = int(input())
arr = list(map(int, input().split()))

# Finding next greater elements
result = find_next_greater_element(arr)

# Print results
for r in result:
    print(r)

Code Explanation

The code above defines a function that finds the next greater element for each element in the given array. The function follows these steps:

  1. Calculate the length of the input array and initialize the result array.
  2. Iterate through the given array from right to left.
  3. Check the top element of the stack for comparison with the current element.
  4. If the top element of the stack is less than or equal to the current element, pop elements from the stack. This ensures only values greater than the current element remain in the stack.
  5. If the stack is not empty, the top element of the stack is the next greater element for the current element. Record this in the result array.
  6. Add the current element to the stack.

Complexity Analysis

The time complexity is O(N). Each element is added to and removed from the stack once, resulting in a total of N operations. The space complexity is O(N), considering the space needed for the result array and the stack.

Example Result

Let's check some test cases for the code. We will use the example provided above to find the next greater elements.


# Input example
# 5
# 2 1 3 4 5

print(find_next_greater_element([2, 1, 3, 4, 5]))  # Output: [3, 3, 4, 5, -1]

Conclusion

In this session, we explored the process of solving the 'Finding Next Greater Element' problem. We efficiently solved the problem using a stack and applied the principle through actual code. This method of problem-solving is very useful in real coding tests and algorithm interviews, so be sure to practice it.

Next time, I will come back with another algorithm problem. Thank you!