C/C++ Coding Exercise – Find Minimum in Rotated Sorted Array – Leetcode Online Judge

Here is another nice coding exercise from Leetcode Online Judge: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Assume a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 may become 4 5 6 7 0 1 2).
There are no duplicate elements in the array, and you are required to find the minimal number.

O(n) naive solution

The easiest solution that get you accepted is to check every element and compare to the current minimal. This approach applies to any array, sorted or unsorted. The accepted code executes at 40ms.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// https://helloacm.com
class Solution {
public:
    int findMin(vector<int> &num) {
        int sz = num.size();
        int min = num[0];
        for (int i = 1; i < sz; i ++) {
            if (num[i] < min) {
                min = num[i];
            }
        }
        return min;
    }
};

// https://helloacm.com
class Solution {
public:
    int findMin(vector<int> &num) {
        int sz = num.size();
        int min = num[0];
        for (int i = 1; i < sz; i ++) {
            if (num[i] < min) {
                min = num[i];
            }
        }
        return min;
    }
};

O(n) improved solution

The array is sorted, and there are no duplicates. There are only a few cases. The first one is the minimal; The minimal number is in the middle; The minimal in the end;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// https://helloacm.com
class Solution {
public:
    int findMin(vector<int> &num) {
        int sz = num.size();
        if (sz == 1) return num[0];
        // the first element is the minimal
        if ((num[0] < num[1]) && (num[0] < num[sz - 1])) return num[0];
        // the last element is the minimal;
        if (num[sz - 2] > num[sz - 1]) return num[sz - 1];
        // it is in the middle
        for (int i = 0; i < sz - 1; i ++) {
            if (num[i] > num[i + 1]) {
                return num[i + 1];
            }
        }
    }
};

// https://helloacm.com
class Solution {
public:
    int findMin(vector<int> &num) {
        int sz = num.size();
        if (sz == 1) return num[0];
        // the first element is the minimal
        if ((num[0] < num[1]) && (num[0] < num[sz - 1])) return num[0];
        // the last element is the minimal;
        if (num[sz - 2] > num[sz - 1]) return num[sz - 1];
        // it is in the middle
        for (int i = 0; i < sz - 1; i ++) {
            if (num[i] > num[i + 1]) {
                return num[i + 1];
            }
        }
    }
};

This approach slightly improves the O(n) code above and it gets accepted for 36ms.

O(log n) binary search

If the number of input is huge then the O(n) approach will be time consuming. The binary search algorithm can be modified to find the minimal given that the array is sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
// https://helloacm.com
public:
    int findMin(vector<int> &num) {
        int left = 0, right = num.size() - 1;
        while (left < right) {
            if (num[left] < num[right]) {
                return num[left];
            }
            int mid = left + (right - left) / 2;
            if (num[mid] >= num[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return num[left];
    }
};

class Solution {
// https://helloacm.com
public:
    int findMin(vector<int> &num) {
        int left = 0, right = num.size() - 1;
        while (left < right) {
            if (num[left] < num[right]) {
                return num[left];
            }
            int mid = left + (right - left) / 2;
            if (num[mid] >= num[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return num[left];
    }
};

The Binary Search is the fastest and the code execution is 20ms (1 time faster).

Featured Comment

Yes , but it is not always necessary true , unless n beyond n(0) point , otherwise linear search can be executed faster. Not even to mention about sorting’s complexity for initiating data set. However if data is very large then is definitely yes — worth to invest a craftier code.

–EOF (The Ultimate Computing & Technology Blog) —