Editorial - STACK14 - Next Smallest element

editorial
1

Explanation

This problem can be solved using a stack data structure. The stack will assist in keeping track of elements that have the possibility of becoming the next smallest element for the upcoming position while traversing from right to left in the array.

When traversing the array from right to left to find the next smaller element for each position, we need to adapt the stack usage slightly. This time the stack will keep track of elements for which we are yet to find a smaller element that appears before them (to their left). Since we’re processing elements from right to left, the next smaller element is guaranteed to appear later in the original list order but earlier in our traversal.

Here’s the updated step-by-step algorithm:

  • Initialize an empty stack s to maintain indices.
  • Traverse the input array from right to left (i.e., start from the last element and
    move towards the first).
  • For each element at index i, do the following:
    • While the stack is not empty and the value at the current top of the stack is greater than or equal to the current element, pop from the stack.
    • If the stack is now empty, it implies there is no smaller element to the left; otherwise, the element at the current top of the stack is the next smaller element for arr[i].
    • Push the index i of the current element onto the stack.
    • Print out the contents for each position immediately or store them in an array and print after the loop based on the requirement.

C++ Solution

#include <iostream>
#include <stack>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

std::vector<int> nextSmallestElement(const std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> result(n, -1); // Initialize result with -1 for elements with no smaller element
    std::stack<int> s; // Stack to store indices

    for (int i = n - 1; i >= 0; --i) { // Iterate from right to left
        while (!s.empty() && arr[i] <= arr[s.top()]) {
            s.pop();
        }
        if(s.size()!=0) {
            result[i] = arr[s.top()];
        }
        s.push(i);
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    vector<int> result = nextSmallestElement(arr);
    for (auto e : result) {
        cout << e << " ";
    }
    return 0;
}

Python Solution

def next_smallest_element(arr):
    n = len(arr)
    result = [-1] * n  # Initialize result with -1 for elements with no smaller element
    stack = []  # Stack to store indices

    for i in range(n - 1, -1, -1):  # Iterate from right to left
        while stack and arr[i] <= arr[stack[-1]]:
            stack.pop()
        if stack:
            result[i] = arr[stack[-1]]
        stack.append(i)

    return result


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    result = next_smallest_element(arr)
    for e in result:
        print(e, end=" ")


if __name__ == "__main__":
    main()

Java Solution

import java.util.Scanner;
import java.util.Stack;

class NextSmallestElement {

    public static int[] nextSmallestElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) { // Iterate from right to left
            while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                result[i] = arr[stack.peek()];
            } else {
                result[i] = -1;
            }
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int[] result = nextSmallestElement(arr);
        for (int e : result) {
            System.out.print(e + " ");
        }
    }
}