Find leftmost smaller number in an array

The problem is to find the leftmost smaller number for each element in a given array. For each element in the array, we need to find the first element to its left that is smaller than the current element. If there is no such element, we denote it as "None."

Problem Statement

Given an array of integers, we need to find the leftmost smaller number for each element and print the results.

Example

Consider the following example:

Input: [5, 6, 4, 7, 3, 10, 6, 2, 4]

Output:

5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2

Idea to Solve the Problem

To find the leftmost smaller number for each element, we can use a stack to keep track of the elements while iterating through the array from left to right. We start by initializing an empty stack called s. We iterate through the array, and for each element, we do the following:

1. While the stack is not empty and the top element of the stack is greater than or equal to the current element, we remove elements from the stack. This step ensures that the stack contains only the elements that are smaller than the current element.
2. If the stack becomes empty after the removal or was initially empty, it means there is no leftmost smaller element for the current element, so we print "None" as the result for the current element.
3. If the stack is not empty after the removal, the top element of the stack is the leftmost smaller element for the current element, so we print the top element as the result for the current element.
4. Finally, we push the current element onto the stack.

Pseudocode

Function leftmostSmaller(arr, n):
    Create an empty stack s

    for i from 0 to n-1:
        while s is not empty and s.peek() >= arr[i]:
            Pop the top element from s
        
        if s is empty:
            Print arr[i] + " : None"
        else:
            Print arr[i] + " : " + s.peek()

        Push arr[i] onto s

Algorithm

1. Create a class called Smaller.
2. Define a function called leftmostSmaller that takes an array arr and its size n as parameters.
3. Create an empty stack called s.
4. Iterate through the array from index 0 to n-1.
5. For each element arr[i], do the following: a. While the stack s is not empty and the top element of the stack s.peek() is greater than or equal to the current element arr[i], do the following: i. Pop the top element from the stack s. b. If the stack s is empty after the removal or was initially empty, it means there is no leftmost smaller element for the current element, so print arr[i] + " : None". c. If the stack s is not empty after the removal, the top element of the stack is the leftmost smaller element for the current element, so print arr[i] + " : " + s.peek(). d. Push the current element arr[i] onto the stack s.
6. The function is now complete.

Code Solution

Here given code implementation process.

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

import java.util.Stack;
/*
    Java program for
    Find leftmost smaller number in an array
*/
public class Smaller
{
    public void leftmostSmaller(int[] arr, int n)
    {
        Stack < Integer > s = new Stack < Integer > ();
        for (int i = 0; i < n; ++i)
        {
            while (!s.isEmpty() && s.peek() >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop();
            }
            if (s.isEmpty())
            {
                // When leftmost smaller elements are not exist
                System.out.print("\n " + arr[i] + " : None");
            }
            else
            {
                System.out.print("\n " + arr[i] + " : " + s.peek());
            }
            // Add new element
            s.push(arr[i]);
        }
    }
    public static void main(String[] args)
    {
        Smaller task = new Smaller();
        int[] arr = {
            5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
        };
        // Get the size of array
        int n = arr.length;
        // Test
        task.leftmostSmaller(arr, n);
    }
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

// Include header file
#include <iostream>
#include <stack>

using namespace std;
/*
    C++ program for
    Find leftmost smaller number in an array
*/
class Smaller
{
    public: void leftmostSmaller(int arr[], int n)
    {
        stack < int > s;
        for (int i = 0; i < n; ++i)
        {
            while (!s.empty() && s.top() >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop();
            }
            if (s.empty())
            {
                // When leftmost smaller elements are not exist
                cout << "\n " << arr[i] << " : None";
            }
            else
            {
                cout << "\n " << arr[i] << " : " << s.top();
            }
            // Add new element
            s.push(arr[i]);
        }
    }
};
int main()
{
    Smaller *task = new Smaller();
    int arr[] = {
        5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
    };
    // Get the size of array
    int n = sizeof(arr) / sizeof(arr[0]);
    // Test
    task->leftmostSmaller(arr, n);
    return 0;
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp program for
    Find leftmost smaller number in an array
*/
public class Smaller
{
    public void leftmostSmaller(int[] arr, int n)
    {
        Stack < int > s = new Stack < int > ();
        for (int i = 0; i < n; ++i)
        {
            while (!(s.Count == 0) && s.Peek() >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.Pop();
            }
            if ((s.Count == 0))
            {
                // When leftmost smaller elements are not exist
                Console.Write("\n " + arr[i] + " : None");
            }
            else
            {
                Console.Write("\n " + arr[i] + " : " + s.Peek());
            }
            // Add new element
            s.Push(arr[i]);
        }
    }
    public static void Main(String[] args)
    {
        Smaller task = new Smaller();
        int[] arr = {
            5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
        };
        // Get the size of array
        int n = arr.Length;
        // Test
        task.leftmostSmaller(arr, n);
    }
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

package main
import "fmt"
/*
    Go program for
    Find leftmost smaller number in an array
*/

func leftmostSmaller(arr[] int, n int) {
    var s [] int
    for i := 0 ; i < n ; i++ {
        for (len(s) != 0 && s[len(s) - 1] >= arr[i]) {
            // Remove element until , 
            // the element is greater than or equal to current element
            s = s[: len(s) - 1]
        }
        if len(s) == 0 {
            // When leftmost smaller elements are not exist
            fmt.Print("\n ", arr[i], " : None")
        } else {
            fmt.Print("\n ", arr[i], " : ", s[len(s) - 1])
        }
        // Add new element
        s = append(s, arr[i])
    }
}
func main() {

    var arr = [] int {5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4}
    // Get the size of array
    var n int = len(arr)
    // Test
    leftmostSmaller(arr, n)
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

<?php
/*
    Php program for
    Find leftmost smaller number in an array
*/
class Smaller
{
    public  function leftmostSmaller($arr, $n)
    {
        $s = array();
        for ($i = 0; $i < $n; ++$i)
        {
            while (!empty($s) && end($s) >= $arr[$i])
            {
                // Remove element until 
                // the element is greater than or equal to current element
                array_pop($s);
            }
            if (empty($s))
            {
                // When leftmost smaller elements are not exist
                echo("\n ".$arr[$i]." : None");
            }
            else
            {
                echo("\n ".$arr[$i]." : ".end($s));
            }
            // Add new element
            array_push($s, $arr[$i]);
        }
    }
}

function main()
{
    $task = new Smaller();
    $arr = array(5, 6, 4, 7, 3, 10, 6, 2, 4);
    // Get the size of array
    $n = count($arr);
    // Test
    $task->leftmostSmaller($arr, $n);
}
main();

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

/*
    Node JS program for
    Find leftmost smaller number in an array
*/
class Smaller
{
    leftmostSmaller(arr, n)
    {
        var s = [];
        for (var i = 0; i < n; ++i)
        {
            while (!(s.length == 0) && s[s.length - 1] >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop();
            }
            if ((s.length == 0))
            {
                // When leftmost smaller elements are not exist
                process.stdout.write("\n " + arr[i] + " : None");
            }
            else
            {
                process.stdout.write("\n " + arr[i] + " : " + s[s.length - 1]);
            }
            // Add new element
            s.push(arr[i]);
        }
    }
}

function main()
{
    var task = new Smaller();
    var arr = [5, 6, 4, 7, 3, 10, 6, 2, 4];
    // Get the size of array
    var n = arr.length;
    // Test
    task.leftmostSmaller(arr, n);
}
main();

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

#    Python 3 program for
#    Find leftmost smaller number in an array
class Smaller :
    def leftmostSmaller(self, arr, n) :
        s = []
        i = 0
        while (i < n) :
            while (not(len(s) == 0) and s[-1] >= arr[i]) :
                #  Remove element until , 
                #  the element is greater than or equal to current element
                s.pop()
            
            if ((len(s) == 0)) :
                #  When leftmost smaller elements are not exist
                print("\n ", arr[i] ," : None", end = "")
            else :
                print("\n ", arr[i] ," : ", s[-1], end = "")
            
            #  Add new element
            s.append(arr[i])
            i += 1
        
    

def main() :
    task = Smaller()
    arr = [5, 6, 4, 7, 3, 10, 6, 2, 4]
    #  Get the size of list
    n = len(arr)
    #  Test
    task.leftmostSmaller(arr, n)

if __name__ == "__main__": main()

  5  : None
  6  :  5
  4  : None
  7  :  4
  3  : None
  10  :  3
  6  :  3
  2  : None
  4  :  2

#    Ruby program for
#    Find leftmost smaller number in an array
class Smaller 
    def leftmostSmaller(arr, n) 
        s = []
        i = 0
        while (i < n) 
            while (!(s.length == 0) && s.last >= arr[i]) 
                #  Remove element until , 
                #  the element is greater than or equal to current element
                s.pop()
            end

            if ((s.length == 0)) 
                #  When leftmost smaller elements are not exist
                print("\n ", arr[i] ," : None")
            else
 
                print("\n ", arr[i] ," : ", s.last)
            end

            #  Add new element
            s.push(arr[i])
            i += 1
        end

    end

end

def main() 
    task = Smaller.new()
    arr = [5, 6, 4, 7, 3, 10, 6, 2, 4]
    #  Get the size of array
    n = arr.length
    #  Test
    task.leftmostSmaller(arr, n)
end

main()

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

import scala.collection.mutable._;
/*
    Scala program for
    Find leftmost smaller number in an array
*/
class Smaller()
{
    def leftmostSmaller(arr: Array[Int], n: Int): Unit = {
        var s: Stack[Int] = new Stack[Int]();
        var i: Int = 0;
        while (i < n)
        {
            while (!s.isEmpty && s.top >= arr(i))
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop;
            }
            if (s.isEmpty)
            {
                // When leftmost smaller elements are not exist
                print("\n " + arr(i) + " : None");
            }
            else
            {
                print("\n " + arr(i) + " : " + s.top);
            }
            // Add new element
            s.push(arr(i));
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: Smaller = new Smaller();
        var arr: Array[Int] = Array(5, 6, 4, 7, 3, 10, 6, 2, 4);
        // Get the size of array
        var n: Int = arr.length;
        // Test
        task.leftmostSmaller(arr, n);
    }
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

import Foundation;
/*
    Swift 4 program for
    Find leftmost smaller number in an array
*/
struct Stack
{
    private
    var items: [Int] = []
    func peek()->Int
    {
        if (self.isEmpty()==false)
        {
            return items.first!
        }
        else
        {
            fatalError("This stack is empty.")
        }
    }
    func isEmpty()->Bool
    {
        return items.count == 0
    }
    mutating func pop()
    {
        items.removeFirst()
    }
    mutating func push(_ data: Int)
    {
        items.insert(data, at: 0)
    }
}
class Smaller
{
    func leftmostSmaller(_ arr: [Int], _ n: Int)
    {
        var s = Stack();
        var i: Int = 0;
        while (i < n)
        {
            while (!s.isEmpty() && s.peek() >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop();
            }
            if (s.isEmpty())
            {
                // When leftmost smaller elements are not exist
                print("\n ", arr[i] ," : None", terminator: "");
            }
            else
            {
                print("\n ", arr[i] ," : ", s.peek(), terminator: "");
            }
            // Add new element
            s.push(arr[i]);
            i += 1;
        }
    }
}
func main()
{
    let task: Smaller = Smaller();
    let arr: [Int] = [5, 6, 4, 7, 3, 10, 6, 2, 4];
    // Get the size of array
    let n: Int = arr.count;
    // Test
    task.leftmostSmaller(arr, n);
}
main();

  5  : None
  6  :  5
  4  : None
  7  :  4
  3  : None
  10  :  3
  6  :  3
  2  : None
  4  :  2

import java.util.Stack;
/*
    Kotlin program for
    Find leftmost smaller number in an array
*/
class Smaller
{
    fun leftmostSmaller(arr: Array < Int > , n: Int): Unit
    {
        val s = Stack < Int > ();
        var i: Int = 0;
        while (i < n)
        {
            while (!s.empty() && s.peek() >= arr[i])
            {
                // Remove element until , 
                // the element is greater than or equal to current element
                s.pop();
            }
            if (s.empty())
            {
                // When leftmost smaller elements are not exist
                print("\n " + arr[i] + " : None");
            }
            else
            {
                print("\n " + arr[i] + " : " + s.peek());
            }
            // Add new element
            s.push(arr[i]);
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val task: Smaller = Smaller();
    val arr: Array < Int > = arrayOf(5, 6, 4, 7, 3, 10, 6, 2, 4);
    // Get the size of array
    val n: Int = arr.count();
    // Test
    task.leftmostSmaller(arr, n);
}

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of elements in the input array arr. This is because we perform a single pass through the array and each element is pushed and popped from the stack at most once. The use of the stack does not significantly affect the overall time complexity.