Find the nearest smaller numbers on left side in an array using stack
Here given code implementation process.
// Java program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class NearestSmaller
{
public void leftSideSmaller(int[] arr, int n)
{
MyStack record = new MyStack();
for (int i = 0; i < n; i++)
{
System.out.print("\n" + arr[i]);
int value = arr[i];
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
System.out.print(" : None");
}
else
{
System.out.print(" : " + record.peek());
}
// Add new element
record.push(arr[i]);
}
}
public static void main(String[] args)
{
NearestSmaller task = new NearestSmaller();
// Array of intger elements
int[] arr = {
3 , 5 , 1 , 7 , 8 , 4 , 6 , 11 , 10 , -1
};
// Get the length
int n = arr.length;
// Test
task.leftSideSmaller(arr, n);
}
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
// Include header file
#include <iostream>
using namespace std;
// C++ program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public:
StackNode *top;
int size;
MyStack()
{
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
// return top element of stack
int peek()
{
return this->top->element;
}
};
class NearestSmaller
{
public: void leftSideSmaller(int arr[], int n)
{
MyStack *record = new MyStack();
for (int i = 0; i < n; i++)
{
cout << "\n" << arr[i];
int value = arr[i];
// Remove all largest element which is exist in top of stack
while (!record->isEmpty() && record->peek() >= value)
{
// Remove the top element
record->pop();
}
if (record->isEmpty())
{
cout << " : None";
}
else
{
cout << " : " << record->peek();
}
// Add new element
record->push(arr[i]);
}
}
};
int main()
{
NearestSmaller *task = new NearestSmaller();
// Array of intger elements
int arr[] = {
3 , 5 , 1 , 7 , 8 , 4 , 6 , 11 , 10 , -1
};
// Get the length
int n = sizeof(arr) / sizeof(arr[0]);
// Test
task->leftSideSmaller(arr, n);
return 0;
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
// Include namespace system
using System;
// Csharp program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class NearestSmaller
{
public void leftSideSmaller(int[] arr, int n)
{
MyStack record = new MyStack();
for (int i = 0; i < n; i++)
{
Console.Write("\n" + arr[i]);
int value = arr[i];
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
Console.Write(" : None");
}
else
{
Console.Write(" : " + record.peek());
}
// Add new element
record.push(arr[i]);
}
}
public static void Main(String[] args)
{
NearestSmaller task = new NearestSmaller();
// Array of intger elements
int[] arr = {
3 , 5 , 1 , 7 , 8 , 4 , 6 , 11 , 10 , -1
};
// Get the length
int n = arr.Length;
// Test
task.leftSideSmaller(arr, n);
}
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
package main
import "fmt"
// Go program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
type StackNode struct {
element int
next * StackNode
}
func getStackNode(element int, next * StackNode) * StackNode {
var me *StackNode = &StackNode {}
me.element = element
me.next = next
return me
}
// Define a custom stack
type MyStack struct {
top * StackNode
size int
}
func getMyStack() * MyStack {
var me *MyStack = &MyStack {}
//Set node values
me.top = nil
me.size = 0
return me
}
// Add node at the top of stack
func(this *MyStack) push(element int) {
this.top = getStackNode(element, this.top)
this.size++
}
func(this MyStack) isEmpty() bool {
if this.size > 0 && this.top != nil {
return false
} else {
return true
}
}
// Remove top element of stack
func(this *MyStack) pop() {
if this.size > 0 && this.top != nil {
var temp * StackNode = this.top
// Change top element of stack
this.top = temp.next
// remove previous top
temp = nil
this.size--
}
}
// return top element of stack
func(this MyStack) peek() int {
return this.top.element
}
type NearestSmaller struct {}
func getNearestSmaller() * NearestSmaller {
var me *NearestSmaller = &NearestSmaller {}
return me
}
func(this NearestSmaller) leftSideSmaller(arr[] int, n int) {
var record * MyStack = getMyStack()
for i := 0 ; i < n ; i++ {
fmt.Print("\n", arr[i])
var value int = arr[i]
// Remove all largest element which is exist in top of stack
for (!record.isEmpty() && record.peek() >= value) {
// Remove the top element
record.pop()
}
if record.isEmpty() {
fmt.Print(" : None")
} else {
fmt.Print(" : ", record.peek())
}
// Add new element
record.push(arr[i])
}
}
func main() {
var task * NearestSmaller = getNearestSmaller()
// Array of intger elements
var arr = [] int {
3,
5,
1,
7,
8,
4,
6,
11,
10,
-1,
}
// Get the length
var n int = len(arr)
// Test
task.leftSideSmaller(arr, n)
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
<?php
// Php program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
public $element;
public $next;
public function __construct($element, $next)
{
$this->element = $element;
$this->next = $next;
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
public function __construct()
{
$this->top = NULL;
$this->size = 0;
}
// Add node at the top of stack
public function push($element)
{
$this->top = new StackNode($element, $this->top);
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != NULL)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = NULL;
$this->size--;
}
}
// return top element of stack
public function peek()
{
return $this->top->element;
}
}
class NearestSmaller
{
public function leftSideSmaller($arr, $n)
{
$record = new MyStack();
for ($i = 0; $i < $n; $i++)
{
echo("\n".$arr[$i]);
$value = $arr[$i];
// Remove all largest element which is exist in top of stack
while (!$record->isEmpty() && $record->peek() >= $value)
{
// Remove the top element
$record->pop();
}
if ($record->isEmpty())
{
echo(" : None");
}
else
{
echo(" : ".$record->peek());
}
// Add new element
$record->push($arr[$i]);
}
}
}
function main()
{
$task = new NearestSmaller();
// Array of intger elements
$arr = array(3, 5, 1, 7, 8, 4, 6, 11, 10, -1);
// Get the length
$n = count($arr);
// Test
$task->leftSideSmaller($arr, $n);
}
main();
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
// Node JS program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
return this.top.element;
}
}
class NearestSmaller
{
leftSideSmaller(arr, n)
{
var record = new MyStack();
for (var i = 0; i < n; i++)
{
process.stdout.write("\n" + arr[i]);
var value = arr[i];
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
process.stdout.write(" : None");
}
else
{
process.stdout.write(" : " + record.peek());
}
// Add new element
record.push(arr[i]);
}
}
}
function main()
{
var task = new NearestSmaller();
// Array of intger elements
var arr = [3, 5, 1, 7, 8, 4, 6, 11, 10, -1];
// Get the length
var n = arr.length;
// Test
task.leftSideSmaller(arr, n);
}
main();
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
# Python 3 program
# Find the nearest smaller numbers on left side in an array using stack
# Stack node
class StackNode :
def __init__(self, element, next) :
self.element = element
self.next = next
# Define a custom stack
class MyStack :
def __init__(self) :
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
return self.top.element
class NearestSmaller :
def leftSideSmaller(self, arr, n) :
record = MyStack()
i = 0
while (i < n) :
print("\n", arr[i], end = "")
value = arr[i]
# Remove all largest element which is exist in top of stack
while (not record.isEmpty() and record.peek() >= value) :
# Remove the top element
record.pop()
if (record.isEmpty()) :
print(" : None", end = "")
else :
print(" : ", record.peek(), end = "")
# Add new element
record.push(arr[i])
i += 1
def main() :
task = NearestSmaller()
# Array of intger elements
arr = [3, 5, 1, 7, 8, 4, 6, 11, 10, -1]
# Get the length
n = len(arr)
# Test
task.leftSideSmaller(arr, n)
if __name__ == "__main__": main()
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
# Ruby program
# Find the nearest smaller numbers on left side in an array using stack
# Stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, n)
self.element = element
self.next = n
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
return self.top.element
end
end
class NearestSmaller
def leftSideSmaller(arr, n)
record = MyStack.new()
i = 0
while (i < n)
print("\n", arr[i])
value = arr[i]
# Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
# Remove the top element
record.pop()
end
if (record.isEmpty())
print(" : None")
else
print(" : ", record.peek())
end
# Add new element
record.push(arr[i])
i += 1
end
end
end
def main()
task = NearestSmaller.new()
# Array of intger elements
arr = [3, 5, 1, 7, 8, 4, 6, 11, 10, -1]
# Get the length
n = arr.length
# Test
task.leftSideSmaller(arr, n)
end
main()
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
// Scala program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode(var element: Int,
var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode,
var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): Int = {
return this.top.element;
}
}
class NearestSmaller()
{
def leftSideSmaller(arr: Array[Int], n: Int): Unit = {
var record: MyStack = new MyStack();
var i: Int = 0;
while (i < n)
{
print("\n" + arr(i));
var value: Int = arr(i);
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
print(" : None");
}
else
{
print(" : " + record.peek());
}
// Add new element
record.push(arr(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: NearestSmaller = new NearestSmaller();
// Array of intger elements
var arr: Array[Int] = Array(3, 5, 1, 7, 8, 4, 6, 11, 10, -1);
// Get the length
var n: Int = arr.length;
// Test
task.leftSideSmaller(arr, n);
}
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
import Foundation;
// Swift 4 program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ next: StackNode? )
{
self.element = element;
self.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty() -> Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek() -> Int
{
return self.top!.element;
}
}
class NearestSmaller
{
func leftSideSmaller(_ arr: [Int], _ n: Int)
{
let record: MyStack = MyStack();
var i: Int = 0;
while (i < n)
{
print("\n", arr[i], terminator: "");
let value: Int = arr[i];
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
print(" : None", terminator: "");
}
else
{
print(" : ", record.peek(), terminator: "");
}
// Add new element
record.push(arr[i]);
i += 1;
}
}
}
func main()
{
let task: NearestSmaller = NearestSmaller();
// Array of intger elements
let arr: [Int] = [3, 5, 1, 7, 8, 4, 6, 11, 10, -1];
// Get the length
let n: Int = arr.count;
// Test
task.leftSideSmaller(arr, n);
}
main();
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
// Kotlin program
// Find the nearest smaller numbers on left side in an array using stack
// Stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, next: StackNode ? )
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): Int
{
return this.top!!.element;
}
}
class NearestSmaller
{
fun leftSideSmaller(arr: Array < Int > , n: Int): Unit
{
val record: MyStack = MyStack();
var i: Int = 0;
while (i < n)
{
print("\n" + arr[i]);
val value: Int = arr[i];
// Remove all largest element which is exist in top of stack
while (!record.isEmpty() && record.peek() >= value)
{
// Remove the top element
record.pop();
}
if (record.isEmpty())
{
print(" : None");
}
else
{
print(" : " + record.peek());
}
// Add new element
record.push(arr[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: NearestSmaller = NearestSmaller();
// Array of intger elements
val arr: Array < Int > = arrayOf(3, 5, 1, 7, 8, 4, 6, 11, 10, -1);
// Get the length
val n: Int = arr.count();
// Test
task.leftSideSmaller(arr, n);
}
Output
3 : None
5 : 3
1 : None
7 : 1
8 : 7
4 : 1
6 : 4
11 : 6
10 : 6
-1 : None
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