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