Find the smallest element in a sorted and rotated array [closed]

Question

I was solving a question asked in interview by Uber. It says:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in \$O(\log n)\$ time. You may assume the array does not contain duplicates.

#include <iostream>

int find_smallest(int a[], int l, int r){
    if (l ==r)
        return a[l];
    else if (l+1 == r)
        return ((a[l] < a[r]) ? a[l] : a[r]);
    else {
        int m = (l + r) / 2;
        int d1 = find_smallest(a, l, m);
        int d2 = find_smallest(a, m+1, r);
        return  ((d1 < d2) ? d1 : d2);
    }
}


int main(){
    int a[] = {5,3,2,5,6,7};
    std::cout << find_smallest(a, 0, 5);
}

Please ignore the hardcoding of values. It was just for testing. Also, is the runtime of the code \$O(\log n)\$?

Answer 1

The input, 1) which doesn't contain duplicates, has been 2) sorted, 3) rotated:

int a[] = {5,3,2,5,6,7};
// removing duplicates gives
int a[] = {5,3,2,6,7};
// sorting gives
int a[] = {2,3,5,6,7};
// rotating gives (for instance):
int a[] = {5,6,7,2,3};

log(n) suggests a divide-and-conquer strategy like binary-search, as you found out by yourself. But what are you looking for in this case? Not a value, but the position where a[n] > a[n+1]. Notice that if a[n] > a[n+1], then also a[0] > a[n+1]: the "direction change" occurred in that range. If not, it occurred in the range [a[n+1], a[len(a)]).

Divide-and-conquer is trickier than it may seem because it's really easy to access the array out-of-bounds. Iterator interfaces likes those of the C++ standard library make it easier and clearer:

template <typename Iterator>
Iterator find_partition_point(Iterator first, Iterator last) {
    if (first == last) return last; // empty array
    if (std::next(first) == last) return first; // one-value array
    if (*first < *std::prev(last)) return first; // null/full rotation
    // so we have at least two elements and a change of direction
    auto pivot = first + std::distance(first, last) / 2;
    if (*pivot < *first) { // direction change in [first, pivot]
        if (*std::prev(pivot) > *pivot) return pivot;
        return find_partition_point(first, pivot);
    }
    return find_partition_point(std::next(pivot), last); // direction change in (pivot, last)
}

Answer 2

The the approach could be as follows (with the added assumption of no duplicates that you ignored in your sample):

1) Check if the first element is smaller than the second one. If so, either the inverted part was the single first element or the second part was inverted. Consequently return the minimum of the first and last element of the array.

2) If not but the last element is smaller than the second-to-last, the whole array was inverted and the last element is the minimum. (not sure if this is allowed)

3) If neither is the case, the first part of the array is decreasing, the second part is increasing and the minimum is the unique element a[i] with a[i-1] > a[i] < a[i+1]. That element can be found in O(log n) implementing a binary search as opposed to your idea of checking both sides again, leading to O(n log n).

Answer 3

Here is my minimal solution about the problem

• the strategy is divide-and-conquer for the reasons already explained by @papagaga

• it is based on the idea that before the rotation the array has this structure

[m .. p P .. M]

with

• m min

• M max

• p pivot

• P next to the pivot so that P>p

• while after the rotation it has the following structure

[P .. M m .. p]

so the idea is to update the l left cursor and r right cursor so that v[l] > v[r] with a divide and conquer strategy so to have O(LogN) complexity and ultimately the final condition is l and r are contiguous and the first identifies M while the second identifies m hence return the last one

EDIT Following @papagaga suggestion I provide 2 implementations

1. Index based solution

#include <iostream>
#include <vector>
using namespace std;

vector<int> a = {5,6,7,8,9,10,11, 1,2,3,4};

unsigned int solve(const vector<int>& a, unsigned int l=0, unsigned int r=0)
{
    if(a.empty()) throw runtime_error("Empty"); 
    if(a.size()==1) return 0; 
    if(r==0) r=a.size()-1; ///< Overwrite the invalid initialization with the right value, unfortunately it is not possible to do this in function declaration 
    if(a[l] < a[r]) return l; ///< Sorted in Ascending Order 
    if(r-l==1) return r; 
    const auto m = (r+l)/2; 
    if(a[m] > a[l]) return solve(a, m, r); 
    return solve(a, l, m); 
}

int main() {
    // your code goes here
    cout << "Min=" << a[solve(a)]; 
    return 0;
}

Comments

• Added the empty array case management using Exception
• An alternative could have been using Maybe Monad (a Boost Optional) to represent non meaningful results

2. Iterators based solution

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

vector<int> a = {5,6,7,8,9,10,11, 1,2,3,4};

vector<int>::iterator solve(const vector<int>::iterator l, const vector<int>::iterator r)
{
    if(l==r) return r; ///< Covers the single element array case 
    if(*l < *r) return l; ///< Sorted in Ascending Order 
    if(r-l==1) return r; 
    const auto m = l + distance(l,r)/2;  
    if(*m > *l) return solve(m, r); 
    return solve(l, m); 
}

int main() {
    // your code goes here
    cout << "Min=" << *solve(a.begin(), a.end()-1); 
    return 0;
}

Comments

• Working with iterators allows to represent invalid values so no need for Exception and explicit Maybe Monad as the iterator type is one
• The first check automatically manages the one element case
• The empty array case should be managed before calling this function as it expects both the iterators point to valid elements

Answer 4

Just to complement the answers from above with one own full example version: Live The comments are in the code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <vector>

template<typename Container>
void print(const Container& c)
// helper function for printing container elements
{
  std::cout << "[ ";
  std::copy(begin(c), end(c), std::ostream_iterator<typename Container::value_type>(std::cout, " "));
  std::cout << "]";
  std::cout << std::endl;
}

template<typename Iter>
void shift(Iter first, Iter last, std::size_t n)
// helper function for left-shiting n-elements in range [first, last)
// uses std::rotate from algorithm-STL
{
  auto nn = n % std::distance(first, last);   // invariant: shifting c.size() times provides the initial sequence
  auto new_first = first;
  std::advance(new_first, nn);                  // new first
  std::rotate(first, new_first, last);
}

template<typename Container>
void left_shift(Container& c, std::size_t n)
// helper function for left-shifting n-elements in container c
{
  shift(begin(c), end(c), n);
}

template<typename Container>
void right_shift(Container& c, std::size_t n)
// helper function for right-shifting n-elements in container c
{
  shift(rbegin(c), rend(c), n);
}

template<typename Iter>
typename Iter::value_type
mmin(Iter first, Iter last)
//
// Assuming non-empty sequence
//
// finds Minimum within sorted shifted container c with log-n complexity
// Assumption:
// 1) container c containes no duplicates
// 2) container c is sorted in asceding order initially: c[n] < c[n+1] (strict < because no duplicates according to 1)
//
// if the sorted container c is shifted
// then there is position k, for which: c[k] > c[k+1]
// ->
// it's not hard to show that: min = c[k+1] is the requested minimum
// and the searched position k for which c[k] > c[k+1]
// is within range [start, end), for which: c[start] > c[end-1];
//
// for example:
// Initial sorted container:
// 0 1 2 3 4 5 6 7 8 - position
// 1 2 3 4 5 6 7 8 9 - elements
//
// shifting to left
// 3 4 5 6 7 8 9 1 2 - c[6] > c[7] = min(c)
//
// shifing to right:
// 7 8 9 1 2 3 4 5 6 - c[2] > c[3] = min(c)
//
// Algorithm for finding minimum:
// we are doing binary search for c[k] > c[k+1] within range [start, end) with c[start] > c[end-1]
// starting from 2 Ranges: 
//  Range1: [start=first, end=(first+last)/2)
//  Range2: [start=(first+last)/2, last)
//
//  and repeating recursively with [first, last) = one of {Range1, Range2} with c[first] > c[last-1]
{
  auto d = std::distance(first, last);

  assert(1 <= d);

  auto p = first + d/2;

  return (d == 1) ? *first   // 1 element
                  : (
                      (*first > *std::next(first)) ? *std::next(first)  // if pivot is beyond minimum
                                                   : (

                                                        (*p > *std::next(p)) ?  *std::next(p)  // minimum
                                                                             : ( (*p > *std::prev(last)) ? mmin(p, last)  // recursive search within new range
                                                                                                         : mmin(first, p) // via divide and conquer
                                                                               )

                                                      )
                      );
}


template<typename SortedShiftedContainer>
typename SortedShiftedContainer::value_type
mmin(const SortedShiftedContainer& c)
{
  return mmin(begin(c), end(c));
}


int main()
{
  std::vector<int> v{1, 2, 3, 4, 5};
  std::cout << "Initial array : ";
  print(v);

  for (std::size_t n = 1; n <= v.size(); ++n)
  {
    auto vv{v};
    left_shift(vv, n);
    std::cout << "min = " << mmin(vv) << ", ";
    std::cout << "for left-shifted " << n << " elements : ";
    print(vv);
  }

  for (std::size_t n = 1; n <= v.size(); ++n)
  {
    auto vv{v};
    right_shift(vv, n);
    std::cout << "min = " << mmin(vv) << ", ";
    std::cout << "for right-shifted " << n << " elements : ";
    print(vv);
  }


}

Answer 5

It ought to be clear that the algorithm inspects every element at least once. Therefore its complexity cannot be less than O(n).

The variable and function names could be much more expressive. Is the interface pre-determined by the challenge, or did you assume that inputs are integers? It would be easier to use if it accepted a standard container, or an iterator pair in the usual way.

The test is flawed, because the input is not a rotation of a sorted array. Also, a single test isn't enough - include more tests, ideally as the functionality is developed.