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
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
}

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

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

   
  }
}

 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);
	}
}

 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();

 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();

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

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

 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);
	}
}

 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();

  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.