C++ Coding Test Course, Finding the Largest Number

In this course, we will solve the problem of “Finding the Next Greater Element” using C++. This problem involves finding the nearest larger number to the right of each element in the given sequence. Through this, we will learn about problem-solving techniques using stacks and efficient algorithm design.

Problem Description

For each element in the given integer array, find the nearest position to the right that has a number larger than that element and output that number. If no such number exists, output -1.

Input

  • The first line contains the size of the array N (1 ≤ N ≤ 1,000,000)
  • The second line contains an array A consisting of N integers (0 ≤ A[i] ≤ 1,000,000)

Output

  • Output an array B consisting of N integers, where B[i] is the closest larger number to the right of A[i]. If no such number exists, output -1.

Example Input


5
2 1 2 4 3

Example Output


4 2 4 -1 -1

Approach to the Problem

The most efficient way to solve this problem is to use a stack data structure. Starting from the end of the array, we traverse each element and perform the following steps.

  1. If the stack is not empty and the current element is greater than the top element of the stack, pop elements from the stack. The popped element at this point becomes the next greater element for the current element.
  2. Store the index of the current element and its next greater value in the array.
  3. Push the current element onto the stack.

By repeating this process until the beginning of the array, we can find the next greater element for all elements.

Time Complexity

The time complexity of this algorithm is O(N). Each element is pushed to and popped from the stack exactly once, so even if we visit all elements, the number of elements in the stack does not exceed N.

Implementation

Now let’s implement the above algorithm in C++.


#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void findNextGreaterElement(const vector<int>& arr, vector<int>& result) {
    stack<int> s; // Stack declaration

    for (int i = arr.size() - 1; i >= 0; --i) {
        // Remove elements from the stack that are less than or equal to the current element
        while (!s.empty() && s.top() <= arr[i]) {
            s.pop();
        }
        // If the stack is empty, the next greater element is -1
        if (s.empty()) {
            result[i] = -1;
        } else {
            result[i] = s.top(); // The top element of the stack is the next greater element
        }
        s.push(arr[i]); // Add the current element to the stack
    }
}

int main() {
    int N;
    cout << "Enter the size of the array: ";
    cin >> N;

    vector<int> arr(N);
    cout << "Enter the array elements: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    vector<int> result(N);
    findNextGreaterElement(arr, result);

    cout << "Next greater elements: ";
    for (int i = 0; i < N; ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation

The above code is a C++ program to solve the “Finding the Next Greater Element” problem. Here is an explanation of each part.

  • Including Header Files: Includes iostream, vector, and stack libraries to enable input/output, vector usage, and stack usage.
  • findNextGreaterElement function: This function takes the input array and a vector to store results, which contains the core logic for finding the next greater elements.
  • main function: The entry point of the program, where it receives the size and elements of the array from the user, calculates the next greater elements, and prints the results.

Conclusion

In this course, we learned how to efficiently solve the “Finding the Next Greater Element” problem using C++. Through the process of finding the next greater element for each element in the array using a stack, we gained an appreciation for the properties of stacks and the efficiency of the algorithm. Ability to utilize such data structures and algorithms is crucial in coding interviews.

As this problem frequently appears in coding tests, it is vital to consider various modified versions of it and to develop problem-solving skills using stacks. Moving forward, engaging with similar problems will allow you to learn various algorithms and data structures.