• 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 min element in Sorted Rotated Array (With Duplicates)

August 4, 2014 by Dhaval Dave

Problem: Find the minimum element in a sorted and rotated array if duplicates are allowed:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2}   output: 0
Algorithm:

This problem can be easily solved in O(n) time complexity buy traversing the whole array and check for minimum element.
Here we are using a different solution which also take O(n) time complexity in worst case but it is more optimized.
Let us look at this approach; we are using a modified version of Binary Search Tree algorithm.

Thanks Dheeraj for  sharing Question and Code  for this .
#include<iostream>
using namespace std;
int mini(int a,int b)
{
    if(a<b) return a;
    else return b;
}
int BST(int A[],int low,int high)
{
    int mid=low+(high–low)/2;
    if(mid == high) return A[mid];
    //if size of sub array is 1
    if(mid < high && mid > low && A[mid] < A[mid + 1] && A[mid –1] > A[mid] )       return A[mid];
    //compare value of mid + 1, mid, mid-1 if they exist
    if(A[mid] > A[high])
    {
        if(A[mid + 1] < A[mid]) return A[mid + 1];
        else return BST(A, mid + 1, high); //check in right sub array
    }
    else if(A[mid] < A[high])
    {
        if(A[mid] < A[mid – 1]) return A[mid];
        else return BST(A , low , mid – 1); //check in left sub array
    }
    else if(A[mid]==A[high])
    {
        return min(BST(A,low,mid–1),BST(A,mid+1,high));// check for minimum     in both left and right sub array and choose minimum of them
    }  
   
}
int main()
{
    int A[]={2, 2, 2, 2, 2, 2, 2, 2,0, 0, 1, 1, 2};
    int n= sizeof(A)/sizeof(A[0]);
    cout<<BST(A,0,n–1)<<endl;
}

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions Tagged With: Array, Binary Search

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

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Binary Tree in Java

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

Generic Object Oriented Stack with Template

Sort Stack in place

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

C Program for TAIL command of UNIX

Serialise Deserialise N-ary Tree

Given a float number convert it into the string WITHOUT using any inbuilt Function

Binary Tree Isomorphic to each other

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Find loop in Singly linked list

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

Find if two rectangles overlap

C++ OOPs Part2

Number of Islands BFS/DFS

Sequence Finder Dynamic Programming

Daughter’s Age VeryGood Puzzle

Linked List V/S Binary Search Tree

Connect n ropes with minimum cost

ADOBE Aptitude C Language Test

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

Maximum path sum between two leaves

Reliance Jio Software Developer Interview Experience

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Python Array String

SAP Off Campus Hiring_ March 2015 Computer Skills

Handle duplicates in Binary Search Tree

Find position of the only set bit

Word Break Problem

Copyright © 2025 · Genesis Framework · WordPress · Log in