• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find Nearest Minimum number in left side in O(n)

May 15, 2016 by Dhaval Dave

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Examples:

Input:  arr[] = {1, 6, 4, 10, 2, 5}
Output:         {-1, 1, 1, 4, 1, 2}
First element ('1') has no element on left side. For 6, 
there is only one smaller element on left side '1'. 
For 10, there are three smaller elements on left side (1,
6 and 4), nearest among the three elements is 4.

Input: arr[] = {1, 3, 0, 2, 5}
Output:        {-1,1,-1, 0, 2}

Expected time complexity is O(n).

As we need to keep minimum value for each element on left side.
We can think like :
1. Left to right iterate,
2. Keep minimum value at each step.
3. Idea is to use Stack ( Refer similar question : Find Minimum Number from Input Elements in O(1) {remember using stack we were achieving this}

The idea is to use a stack. Stack is used to maintain a subsequence of the values that have been processed so far and are smaller than any later value that has already been processed.

Below is stack based algorithm

Let input sequence be 'arr[]' and size of array be 'n'

1) Create a new empty stack S

2) For every element 'arr[i]' in the input sequence 'arr[]',
   where 'i' goes from 0 to n-1.
    a) while S is nonempty and the top element of 
       S is greater than or equal to 'arr[i]':
           pop S
    
    b) if S is empty:
           'arr[i]' has no preceding smaller value
    c) else:
           the nearest smaller value to 'arr[i]' is 
           the top element of S

    d) push 'arr[i]' onto S

We can think to code it like below from above discussed algorithm and stepsĀ  for finding nearest minimum number left side in array.

#include 
#include 
using namespace std;
 
void printLeftSmaller(int arr[], int n)
{
    stack S;
    for (int i=0; i<n; i++) { while (!S.empty() && S.top() >= arr[i])
            S.pop();
        if (S.empty())
            cout << "-1, ";
        else  
        //Else print the nearest smaller element
            cout << S.top() << ", ";
        S.push(arr[i]);
    }
}
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {1, 3, 0, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printLeftSmaller(arr, n);
    return 0;
}

To find Minimum number Left side of array , we can try above mentioned code.
Instead Array , similar approach we can think for Linked Lists as well.

Time Complexity : O(n)
Space Complexity : O(n)

To contribute to Gohired.in please mail to admin@gohired.in, w’ll represent your approach/ solution with your name to enhance your CV

Similar Articles

Filed Under: Adobe Interview Questions, Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array, Stack

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Trie Dictionary

SAP Off Campus Hiring_ March 2015 Computer Skills

Python Dictionaries

Microsoft BING Interview Experience

System Design: Designing a LLD for Hotel Booking

Naurki.com Security Breach

Word Break Problem

Advanced SQL Injection

Introduction To Number Theory ( Part 1 )

Apriori algorithm C Code Data Mining

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Printing intermediate Integers between one element & next element of array

LeetCode: Binary Tree Maximum Path Sum

Implement a generic binary search algorithm for Integer Double String etc

Circular Linked List

Max Sum in circularly situated Values

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

The greedy coins game Dynamic Programming

BlueStone E-commerce Interview Experience

Print vertical sum of all the axis in the given binary tree

Client Server C program

Serialise Deserialise N-ary Tree

BFS (Breath First Search)

Convert number to words java

Trapping Rain Water

Daughter’s Age VeryGood Puzzle

HackeEarth Flipkart’s Drone

Get K Max and Delete K Max in stream of incoming integers

Test Cases for Round Function

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Copyright © 2025 · Genesis Framework · WordPress · Log in