Next Smaller Element šŸŽÆ

beginner
22 min

Next Smaller Element šŸŽÆ

Welcome to our tutorial on the Next Smaller Element (NSE)! This concept is a crucial part of data structures and algorithms that helps us find the next smaller element for each element in an array. Let's dive in and understand its importance with practical examples. šŸ“

Table of Contents

  1. Introduction
  2. Motivation
  3. Problem Statement
  4. Solution Approaches
    • 4.1 Brute Force Approach
    • 4.2 Efficient Approach
  5. Implementing the Efficient Approach
    • 5.1 Using Stack
    • 5.2 Using Queue
  6. Practical Examples
  7. Quiz

1. Introduction šŸ“

The Next Smaller Element (NSE) problem asks us to find the first occurrence of an element that is smaller than the current element in an array. This is a fundamental concept in data structures and algorithms and has numerous real-world applications.

2. Motivation šŸ’”

Imagine having a stack of cards with numbers on them. You want to sort these cards in ascending order. To do so, you'll need to find the smallest card on top of each card in the stack. This is exactly what the NSE problem solves!

3. Problem Statement šŸ“

Given an array arr[] of n integers, the task is to find the Next Smaller Element (NSE) for each element in the array. The Next Smaller Element for an element x is the smallest element to the right of x that is less than x. If there is no such element, consider the Next Smaller Element as -1.

4. Solution Approaches šŸ“

We will discuss two main approaches to solve the Next Smaller Element problem:

  • Brute Force Approach
  • Efficient Approach

4.1 Brute Force Approach

This approach involves comparing each element with all the elements to its right. Although it works, it has a time complexity of O(n^2), which is too slow for large arrays.

4.2 Efficient Approach

This approach uses a data structure (either a stack or a queue) to keep track of elements that are smaller than the current element. This method has a time complexity of O(n).

5. Implementing the Efficient Approach šŸ“

5.1 Using Stack

In this approach, we maintain a stack that keeps track of elements smaller than the current element. We traverse the array from right to left, popping elements from the stack when their corresponding element in the array is larger.

python
def nextSmaller(arr, n): stack = [] result = [0]*n for i in range(n): while stack and arr[i] < stack[-1]: stack.pop() if stack: result[stack[-1]] = arr[i] stack.append(arr[i]) while stack: result[stack[-1]] = -1 stack.pop() return result

5.2 Using Queue

In this approach, we maintain a queue that keeps track of elements smaller than the current element. The algorithm works in a similar fashion as the stack approach, but with the advantage of constant time (O(1)) insertion and deletion of elements in the queue.

6. Practical Examples šŸ“

Let's try solving some examples to solidify our understanding of the Next Smaller Element problem:

  1. Example 1: Find the Next Smaller Element for the array [4, 5, 2, 25, 7, 1, 22, 18, 3, 12, 6].

    Solution: [2, 5, -1, 7, 1, 22, 18, 3, 12, 6, -1].

  2. Example 2: Implement the problem using the queue-based approach.

    Solution: Implement a similar version of the above algorithm using a queue instead of a stack.

7. Quiz šŸ“

Quick Quiz
Question 1 of 1

What is the time complexity of the Brute Force Approach for the Next Smaller Element problem?