Posted on by Kalkicode
Code Stack

# 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.

``````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());
}
s.push(arr[i]);
}
}
public static void main(String[] args)
{
int[] arr = {
5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
};
// Get the size of array
int n = arr.length;
// Test
}
}``````

#### 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();
}
s.push(arr[i]);
}
}
};
int main()
{
int arr[] = {
5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
};
// Get the size of array
int n = sizeof(arr) / sizeof(arr[0]);
// Test
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());
}
s.Push(arr[i]);
}
}
public static void Main(String[] args)
{
int[] arr = {
5 , 6 , 4 , 7 , 3 , 10 , 6 , 2 , 4
};
// Get the size of array
int n = arr.Length;
// Test
}
}``````

#### 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])
}
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));
}
array_push(\$s, \$arr[\$i]);
}
}
}

function main()
{
\$arr = array(5, 6, 4, 7, 3, 10, 6, 2, 4);
// Get the size of array
\$n = count(\$arr);
// Test
}
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]);
}
s.push(arr[i]);
}
}
}

function main()
{
var arr = [5, 6, 4, 7, 3, 10, 6, 2, 4];
// Get the size of array
var n = arr.length;
// Test
}
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 = "")

s.append(arr[i])
i += 1

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

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

s.push(arr[i])
i += 1
end

end

end

def main()
arr = [5, 6, 4, 7, 3, 10, 6, 2, 4]
#  Get the size of array
n = arr.length
#  Test
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);
}
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
}
}``````

#### 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: "");
}
s.push(arr[i]);
i += 1;
}
}
}
func main()
{
let arr: [Int] = [5, 6, 4, 7, 3, 10, 6, 2, 4];
// Get the size of array
let n: Int = arr.count;
// Test
}
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());
}
s.push(arr[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
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
}``````

#### Output

`````` 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.

## 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.

Categories
Relative Post