• 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

Urban Ladder Written Test.

Minimum insertions to form a palindrome

Find loop in Singly linked list

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Wrong Directions given find minimum moves so that he can reach to the destination

Sequence Finder Dynamic Programming

Amazon Interview On-Campus For Internship – 1

Find if a binary tree is height balanced ?

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

Test Cases for Round Function

Circular Linked List

Hackerearth : Counting Subarrays

Binary Tree in Java

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Find the kth number with prime factors 3, 5 and 7

flattens 2 D linked list to a single sorted link list

Reversal of LinkedList

Print Power Set of a Set

Longest Increasing Subsequence

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Find the element that appears once others appears thrice

Binary Tree Isomorphic to each other

SAP Hiring Off-Campus General Aptitude

Generate next palindrome number

Maximum path sum between two leaves

Stock Buy Sell to Maximize Profit

Maximum of all subarrays of size k

C Program for TAIL command of UNIX

Spanning Tree

Print all nodes that are at distance k from a leaf node

Copyright © 2025 · Genesis Framework · WordPress · Log in