Data Structures and Algorithms: Previous Smaller Element 🎯

Welcome to this comprehensive lesson on Data Structures and Algorithms! In this tutorial, we will delve into the concept of the "Previous Smaller Element" (PSE), a vital algorithmic concept useful in various real-world scenarios.

Understanding the Previous Smaller Element 📝

The Previous Smaller Element of an element x in a list is the first element to the left of x (if any) that is smaller than x. This concept is crucial in sorting algorithms, stack operations, and problem-solving techniques.

💡 Pro Tip: The PSE can help us find the next smaller element in a sorted array, which is an essential problem in competitive programming.

PSE Example 💡

Let's consider a simple array:

[10, 4, 3, 7, 2, 5]

In this array, the PSE for each element is as follows:

10 has no PSE since it's the largest number.
4 has a PSE of 3 (since 3 is the first number to the left of 4 that's smaller).
3 has no PSE since there's no number to the left that's smaller.
7 has a PSE of 4.
2 has a PSE of 3.
5 has no PSE since there's no number to the left that's smaller.

Finding the Previous Smaller Element 💡

To find the PSE of an element, we will traverse the array from left to right, keeping track of the current element and its PSE. Here's a step-by-step guide:

Initialize the current element and its PSE as the first element of the array.
Traverse the array from left to right.
If the current element is smaller than the next element, update the PSE of the current element.
Move to the next element.
Repeat steps 2-4 until you reach the end of the array.

Code Example 💻

python

def find_pses(arr):
    n = len(arr)
    pses = [0]*n  # Initialize an array to store PSEs
    stack = []

    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            pses[stack.pop()] = arr[i]

        stack.append(i)

    while stack:
        pses[stack.pop()] = -1

    return pses

arr = [10, 4, 3, 7, 2, 5]
print(find_pses(arr))  # Output: [0, 3, -1, 4, 3, -1]

In this example, we used a stack to keep track of the current element and its PSE efficiently. The find_pses() function returns the PSE array for the given input array.

Practice and Quiz 📝

Now that you've learned the basics of the Previous Smaller Element, it's time to test your knowledge!