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:
- 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.
- 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.
- 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.
- 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
- Create a class called
Smaller
. - Define a function called
leftmostSmaller
that takes an arrayarr
and its sizen
as parameters. - Create an empty stack called
s
. - Iterate through the array from index 0 to n-1.
- For each element
arr[i]
, do the following: a. While the stacks
is not empty and the top element of the stacks.peek()
is greater than or equal to the current elementarr[i]
, do the following: i. Pop the top element from the stacks
. b. If the stacks
is empty after the removal or was initially empty, it means there is no leftmost smaller element for the current element, so printarr[i] + " : None"
. c. If the stacks
is not empty after the removal, the top element of the stack is the leftmost smaller element for the current element, so printarr[i] + " : " + s.peek()
. d. Push the current elementarr[i]
onto the stacks
. - 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());
}
// 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
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.
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