• 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

Fibonacci Hashing & Fastest Hashtable

Find the smallest window in a string containing all characters of another string

Maximum sum contiguous subarray of an Array

Level order traversal in Spiral form

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

Find loop in Singly linked list

Advanced SQL Injection

Number of Islands BFS/DFS

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

SAP Hiring Off-Campus General Aptitude

DFS (Depth First Search)

VMWare SDEII Interview

Leetcode: Edit Distance

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

Longest Increasing Subsequence

TicTacToe Game As Asked in Flipkart

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

VMWare Openings

Doubly linked list

Printing Longest Common Subsequence

Regular Expression Matching

Binary Tree Isomorphic to each other

Amazon Interview On-Campus For Internship – 1

Word Break Problem

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Serialise Deserialise N-ary Tree

Possible sizes of bus to carry n groups of friends

Diagonal Traversal of Binary Tree

Count Possible Decodings of a given Digit Sequence

Convert number to words java

Copyright © 2025 · Genesis Framework · WordPress · Log in