Posted on by Kalkicode
Code Array

# 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

1. Create a function `smaller(arr, location)` that takes an array and an index `location` as input. Initialize `index` to -1, which will store the index of the nearest smaller element.
2. In a loop, iterate from `location-1` to 0 (inclusive) in decreasing order. For each index `i`:
• Check if `arr[i]` is smaller than `arr[location]`. If it is, update `index` to `i` and break out of the loop.
3. Return the value of `index`.
4. Create a function `nearest_smaller(arr, size)` that takes an array and its size as input.
5. In a loop, iterate through each element of the array using an index `i`.
• Call the `smaller` function with the current index `i` 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.
6. 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.

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

Categories
Relative Post