• 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

Printing intermediate Integers between one element & next element of array

Stickler thief

How strtok() Works

Given a sorted array and a number x, find the pair in array whose sum is closest to x

FizzBuzz Solution C C++

Urban Ladder Written Test.

VMWare Openings

C++ OOPs Part2

Trapping Rain Water

C++ OOPs Part1

ADOBE Aptitude C Language Test

Check Binary Tree is Binary Search Tree or not

Find the number ABCD such that when multipled by 4 gives DCBA.

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Implement LRU Cache

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

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

SAP Hiring Off-Campus General Aptitude

SAP Off Campus Hiring_ March 2015 Computer Skills

SAP Off Campus Hiring_ March 2015 Sample Questions

Interfaces in C++ (Abstract Classes in C++)

Find Percentage of Words matching in Two Strings

Stock Buy Sell to Maximize Profit

Longest Increasing Subsequence

The greedy coins game Dynamic Programming

Leetcode: Merge Intervals

Maximum occurred Smallest integer in n ranges

Find two non repeating elements in an array of repeating elements

Flipkart Set 1 On Campus with Answers

How Radix sort works

Copyright © 2025 · Genesis Framework · WordPress · Log in