Skip to main content

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