Find the nearest smaller element on left side in an array
The problem being addressed is finding the nearest smaller element on the left side of each element in an array of integers. This task involves examining the array elements one by one and identifying the closest element that is smaller than the current element. This operation can be helpful in scenarios such as stock market analysis or optimizing certain algorithms.
Problem Statement and Description
Given an array of integers, the goal is to determine, for each element, the nearest element on its left side that is
smaller than the current element. For example, consider the array [5, 6, 4, 7, 3, 10, 6, 2, 4]
. For
each element in this array, we want to find the nearest smaller element on its left side. The output will be a list
of elements and their corresponding nearest smaller elements (or "None" if no such element exists).
Idea to Solve the Problem
To find the nearest smaller element on the left side for each element in the array, we can iterate through the array and for each element, search to its left for the nearest smaller element. We can do this by comparing the current element with elements to its left until we find a smaller element or reach the beginning of the array.
Pseudocode
smaller(arr, location):
index = -1
for i from location-1 to 0 (decreasing order):
if arr[i] < arr[location]:
index = i
break
return index
nearest_smaller(arr, size):
for i from 0 to size-1:
position = smaller(arr, i)
if position == -1:
print arr[i], " : None"
else:
print arr[i], " : ", arr[position]
Algorithm Explanation
- Create a function
smaller(arr, location)
that takes an array and an indexlocation
as input. Initializeindex
to -1, which will store the index of the nearest smaller element. - In a loop, iterate from
location-1
to 0 (inclusive) in decreasing order. For each indexi
:- Check if
arr[i]
is smaller thanarr[location]
. If it is, updateindex
toi
and break out of the loop.
- Check if
- Return the value of
index
. - Create a function
nearest_smaller(arr, size)
that takes an array and its size as input. - In a loop, iterate through each element of the array using an index
i
.- Call the
smaller
function with the current indexi
as an argument to find the index of the nearest smaller element on the left side. - If the returned index is -1, print "None" for the current element. Otherwise, print the value of the nearest smaller element.
- Call the
- Execute the
nearest_smaller
function with the given array and its size.
Program
//C Program
//Find the nearest smaller element on left side in an array
#include <stdio.h>
//Returning the location of left nearest smallest element
int smaller(int arr[],int location)
{
int i = 0;
int index=-1;
for (i = location-1; i >= 0 && index==-1; --i)
{
if(arr[i] < arr[location])
{
//When smaller elements are exist
index = i;
}
}
return index;
}
//Find the nearest left smaller element of array
void nearest_smaller(int arr[],int size)
{
int position=0;
for (int i = 0; i < size; ++i)
{
position = smaller(arr,i);
if(position==-1)
{
printf("%d : None\n",arr[i] );
}
else
{
//When find left smallest element
printf("%d : %d\n",arr[i],arr[position] );
}
}
}
int main()
{
//Define collection of array elements
int arr[] = {5, 6, 4, 7 , 3, 10, 6, 2, 4};
//Get the size of array
int size=sizeof(arr)/sizeof(arr[0]);
nearest_smaller(arr,size);
return 0;
}
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
/*
C++ Program
Find the nearest smaller element on left side in an array
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Returning the location of left nearest smallest element
int smaller(int arr[], int location) {
int i = 0;
int index = -1;
for (i = location - 1; i >= 0 && index == -1; --i) {
if (arr[i] < arr[location]) {
//When smaller elements are exist
index = i;
}
}
return index;
}
//Find the nearest left smaller element of array
void nearest_left_small(int arr[], int size) {
int position = 0;
for (int i = 0; i < size; ++i) {
position = this->smaller(arr, i);
if (position == -1) {
cout << " " << arr[i] << " : None\n";
} else {
//When find left smallest element
cout << " " << arr[i] << " : " << arr[position] << "\n";
}
}
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
5,
6,
4,
7,
3,
10,
6,
2,
4
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.nearest_left_small(arr, size);
return 0;
}
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
/*
Java Program
Find the nearest smaller element on left side in an array
*/
public class MyArray {
//Returning the location of left nearest smallest element
public int smaller(int []arr,int location)
{
int i = 0;
int index=-1;
for (i = location-1; i >= 0 && index==-1; --i)
{
if(arr[i] < arr[location])
{
//When smaller elements are exist
index = i;
}
}
return index;
}
//Find the nearest left smaller element of array
public void nearest_left_small(int []arr,int size)
{
int position=0;
for (int i = 0; i < size; ++i)
{
position = smaller(arr,i);
if(position==-1)
{
System.out.print(" "+arr[i]+" : None\n" );
}
else
{
//When find left smallest element
System.out.print(" "+arr[i]+" : "+arr[position]+"\n" );
}
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define collection of array elements
int []arr = {5, 6, 4, 7 , 3, 10, 6, 2, 4};
//Get the size of array
int size = arr.length;
obj.nearest_left_small(arr,size);
}
}
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
/*
C# Program
Find the nearest smaller element on left side in an array
*/
using System;
public class MyArray {
//Returning the location of left nearest smallest element
public int smaller(int[] arr, int location) {
int i = 0;
int index = -1;
for (i = location - 1; i >= 0 && index == -1; --i) {
if (arr[i] < arr[location]) {
//When smaller elements are exist
index = i;
}
}
return index;
}
//Find the nearest left smaller element of array
public void nearest_left_small(int[] arr, int size) {
int position = 0;
for (int i = 0; i < size; ++i) {
position = smaller(arr, i);
if (position == -1) {
Console.Write(" " + arr[i] + " : None\n");
} else {
Console.Write(" " + arr[i] + " : " + arr[position] + "\n");
}
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define collection of array elements
arr = {
5,
6,
4,
7,
3,
10,
6,
2,
4
};
//Get the size of array
int size = arr.Length;
obj.nearest_left_small(arr, size);
}
}
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
<?php
/*
Php Program
Find the nearest smaller element on left side in an array
*/
class MyArray {
//Returning the location of left nearest smallest element
public function smaller($arr, $location) {
$i = 0;
$index = -1;
for ($i = $location - 1; $i >= 0 && $index == -1; --$i) {
if ($arr[$i] < $arr[$location]) {
//When smaller elements are exist
$index = $i;
}
}
return $index;
}
//Find the nearest left smaller element of array
public function nearest_left_small($arr, $size) {
$position = 0;
for ($i = 0; $i < $size; ++$i) {
$position = $this->smaller($arr, $i);
if ($position == -1) {
echo(" ". $arr[$i] ." : None\n");
} else {
//When find left smallest element
echo(" ". $arr[$i] ." : ". $arr[$position] ."\n");
}
}
}
}
function main() {
$obj = new MyArray();
//Define collection of array elements
$arr = array(5, 6, 4, 7, 3, 10, 6, 2, 4);
//Get the size of array
$size = count($arr);
$obj->nearest_left_small($arr, $size);
}
main();
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
/*
Node Js Program
Find the nearest smaller element on left side in an array
*/
class MyArray {
//Returning the location of left nearest smallest element
smaller(arr, location) {
var i = 0;
var index = -1;
for (i = location - 1; i >= 0 && index == -1; --i) {
if (arr[i] < arr[location]) {
//When smaller elements are exist
index = i;
}
}
return index;
}
//Find the nearest left smaller element of array
nearest_left_small(arr, size) {
var position = 0;
for (var i = 0; i < size; ++i) {
position = this.smaller(arr, i);
if (position == -1) {
process.stdout.write(" " + arr[i] + " : None\n");
} else {
//When find left smallest element
process.stdout.write(" " + arr[i] + " : " + arr[position] + "\n");
}
}
}
}
function main(args) {
var obj = new MyArray();
//Define collection of array elements
var arr = [5, 6, 4, 7, 3, 10, 6, 2, 4];
//Get the size of array
var size = arr.length;
obj.nearest_left_small(arr, size);
}
main();
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
# Python 3 Program
# Find the nearest smaller element on left side in an array
class MyArray :
# Returning the location of left nearest smallest element
def smaller(self, arr, location) :
i = 0
index = -1
i = location - 1
while (i >= 0 and index == -1) :
if (arr[i] < arr[location]) :
# When smaller elements are exist
index = i
i -= 1
return index
# Find the nearest left smaller element of array
def nearest_left_small(self, arr, size) :
position = 0
i = 0
while (i < size) :
position = self.smaller(arr, i)
if (position == -1) :
print(" ", arr[i] ," : None\n", end = "")
else :
print(" ", arr[i] ," : ", arr[position] ,"\n", end = "")
i += 1
def main() :
obj = MyArray()
# Define collection of array elements
arr = [5, 6, 4, 7, 3, 10, 6, 2, 4]
# Get the size of array
size = len(arr)
obj.nearest_left_small(arr, size)
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
# Find the nearest smaller element on left side in an array
class MyArray
# Returning the location of left nearest smallest element
def smaller(arr, location)
i = 0
index = -1
i = location - 1
while (i >= 0 && index == -1)
if (arr[i] < arr[location])
# When smaller elements are exist
index = i
end
i -= 1
end
return index
end
# Find the nearest left smaller element of array
def nearest_left_small(arr, size)
position = 0
i = 0
while (i < size)
position = self.smaller(arr, i)
if (position == -1)
print(" ", arr[i] ," :None\n")
else
print(" ", arr[i] ," :", arr[position] ,"\n")
end
i += 1
end
end
end
def main()
obj = MyArray.new()
# Define collection of array elements
arr = [5, 6, 4, 7, 3, 10, 6, 2, 4]
# Get the size of array
size = arr.length
obj.nearest_left_small(arr, size)
end
main()
Output
5 :None
6 :5
4 :None
7 :4
3 :None
10 :3
6 :3
2 :None
4 :2
/*
Scala Program
Find the nearest smaller element on left side in an array
*/
class MyArray {
//Returning the location of left nearest smallest element
def smaller(arr: Array[Int], location: Int): Int = {
var i: Int = 0;
var index: Int = -1;
i = location - 1;
while (i >= 0 && index == -1) {
if (arr(i) < arr(location)) {
//When smaller elements are exist
index = i;
}
i -= 1;
}
return index;
}
//Find the nearest left smaller element of array
def nearest_left_small(arr: Array[Int], size: Int): Unit = {
var position: Int = 0;
var i: Int = 0;
while (i < size) {
position = this.smaller(arr, i);
if (position == -1) {
print(" " + arr(i) + " : None\n");
} else {
print(" " + arr(i) + " : " + arr(position) + "\n");
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
//Define collection of array elements
val arr: Array[Int] = Array(5, 6, 4, 7, 3, 10, 6, 2, 4);
//Get the size of array
val size: Int = arr.length;
obj.nearest_left_small(arr, size);
}
}
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
/*
Swift Program
Find the nearest smaller element on left side in an array
*/
class MyArray {
//Returning the location of left nearest smallest element
func smaller(_ arr: [Int], _ location: Int) -> Int {
var i: Int = 0;
var index: Int = -1;
i = location - 1;
while (i >= 0 && index == -1) {
if (arr[i] < arr[location]) {
//When smaller elements are exist
index = i;
}
i -= 1;
}
return index;
}
//Find the nearest left smaller element of array
func nearest_left_small(_ arr: [Int], _ size: Int) {
var position: Int = 0;
var i: Int = 0;
while (i < size) {
position = self.smaller(arr, i);
if (position == -1) {
print(" ", arr[i] ," : None\n", terminator: "");
} else {
print(" ", arr[i] ," : ", arr[position] ,"\n", terminator: "");
}
i += 1;
}
}
}
func main() {
let obj: MyArray = MyArray();
//Define collection of array elements
let arr: [Int] = [5, 6, 4, 7, 3, 10, 6, 2, 4];
//Get the size of array
let size: Int = arr.count;
obj.nearest_left_small(arr, size);
}
main();
Output
5 : None
6 : 5
4 : None
7 : 4
3 : None
10 : 3
6 : 3
2 : None
4 : 2
Time Complexity Analysis
For each element in the array, the algorithm searches through the elements to its left to find the nearest smaller element. In the worst case, this results in a linear search of elements in the left portion of the array. Therefore, the time complexity of this algorithm is O(n^2), where n is the size of the input array.
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