Skip to main content

Find leftmost smaller number in an array

Given an array which includes integer element, Our goal is to find leftmost smallest element of this are which is exists on its left side in array.

 Input arr = {14 , 5 , 9 , 8 , 4 , -2 , 6 , 17 , -1, 10 , 3}

 Output :
 14 : None
 5 : None
 9 : 5
 8 : 5
 4 : None
 -2 : None
 6 : -2
 17 : -2
 -1 : -2
 10 : -2
 3 : -2

Here given code implementation process.

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);
    }
}

Output

 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;
}

Output

 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);
    }
}

Output

 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)
}

Output

 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();

Output

 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();

Output

 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()

Output

  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()

Output

 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);
    }
}

Output

 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();

Output

  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);
}

Output

 5 : None
 6 : 5
 4 : None
 7 : 4
 3 : None
 10 : 3
 6 : 3
 2 : None
 4 : 2
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment