4
\$\begingroup\$

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)\$?

\$\endgroup\$

closed as unclear what you're asking by esote, user673679, Mast, t3chb0t, pacmaninbw Apr 29 at 16:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    \$\begingroup\$ Your testing array is not sorted-and-rotated. And the time complexity is not \$O(\log n)\$, but rather \$O(n\log n)\$. \$\endgroup\$ – vnp Apr 22 at 18:51
3
\$\begingroup\$

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)
}
\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ It's clearly and cleverly explained but there is a bug in your code if I'm not mistaken: it will return the maximum value if the array is sorted (e.g after a null or a full rotation) + the drawback of an index-based design: an artificial and misleading "failure" value (0 isn't the minimum value in an empty range) \$\endgroup\$ – papagaga Apr 23 at 11:52
  • \$\begingroup\$ Yes, but I have specified it relies on the P>p assumption which is not verified in case the array is sorted (so null or full rotation). Anyway I'll close this corner case as well with a simple check at the beginning so thanks for finding this The return 0 is not an error: if the array has 1 element then it is also the min I have not managed the a.size==0 case on purpose as I did not want to make the code slightly less readable adding a runtime_error \$\endgroup\$ – Nicola Bernini Apr 23 at 11:59
  • \$\begingroup\$ Ok, I had misinterpreted the return value (thought it was the value, not its position). Nonetheless, it means you can't handle an empty array. Try to reformulate your code with iterators, you'll see you'll handle the corner cases better and avoid the default values gymnastics \$\endgroup\$ – papagaga Apr 23 at 12:09
  • \$\begingroup\$ > if(a.size()==1) return 0; if(r==0) r=a.size()-1; Not sure if it's in the right order... \$\endgroup\$ – papagaga Apr 23 at 12:13
  • \$\begingroup\$ Hi @papagaga I have edited my answer showing how I’d manage the empty array case when working with index hence relying on Exception, then I have also followed your suggestion including an iterators based solution \$\endgroup\$ – Nicola Bernini Apr 23 at 13:46
0
\$\begingroup\$

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);
  }


}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.