STACK14 - Editorial

editorial
, ,
1

Problem Link - Next Smaller Element

Problem Statement:

Find the next smaller element for each element in an array. For each element, you need to find the next element to the right that is smaller than the current element.

Approach:

The key idea is to utilize a stack to efficiently determine the NSE while iterating through the array from right to left. This approach is effective because, By starting from the end of the array, we ensure that when we check an element, all elements to its right have already been processed. This allows us to easily find the smallest element that follows it.

Here’s a detailed breakdown:

  1. Initialization: We create a result array initialized with -1, indicating that if no smaller element is found, it will default to -1. We also initialize an empty stack to help track the indices of the elements.

  2. Processing Each Element: As we iterate through the array from the last index to the first:

    • For each current element, we first check the stack to see if the top element is larger than or equal to the current element. If it is, we pop the stack. This step ensures that we only keep smaller elements in the stack for potential future comparisons.

  3. Finding the NSE: After popping larger elements, if the stack is not empty, the element at the index stored at the top of the stack is the NSE for the current element. We store this in our result array.

  4. Updating the Stack: Finally, we push the current index onto the stack. This index will serve as a potential NSE for the next elements we process to the left.

  5. Output the Result: Once we have processed all elements, we print the result array, which contains the NSE for each element.

This method is efficient because each element is pushed and popped from the stack at most once, allowing us to find the NSE in linear time.

Time Complexity:

The time complexity is O(n) because we traverse the array once, and each element is handled a limited number of times.

Space Complexity:

The space complexity is O(n) due to the storage used for the result array and the stack that holds indices.