Sorted but rotated array

Question

Given a sorted but rotated array how do you find the pivot ? I was asked this question in an interview. What is a rotated array ?

I got this on internet but its not clear at all.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted.

Pivot is the element which is lesser then in left element and right element as well.

Answer 1

I think a sorted, rotated array is something like this:

Sorted:

2, 7, 32, 48, 55

Rotated:

 32, 48, 55, 2, 7

2 is the pivot. You need to find the position of the pivot.

Solution should be simple: the pivot is the point where the sorting ends and starts again. This is also what you "found on the Internet":

(assuming array is sorted in ascending order. If descending order, change < to >)

for (i = 0; i<array.length; i++)
{
    if array[i+1] < array[i]
        return i + 1;
        break;
}

Added: A divide and conquer logic that I could quickly think of. Keep spliting the array as long as the first element is larger than the last element. If the first element of the split (sub) array is not larger than the last element, the first is the pivot of the original array.

int left = 0;
int right = array.length - 1;
while (array[left] > array[right])
{
    int mid = left + (left + right) / 2;
    if(array[mid] > array[right])
    {
        left = mid + 1;
    }
    else
    {
        right = mid;
    }
}
return left;

BTW, if you were asked this question in an interview, and you did not know what a sorted rotated array is, you can ask. If the interviewer explain it to you and then you give them a solution, you should be good. Personally I wouldn't care if someone does not know terminology. As long as they can think, find logic and code, it should be fine.

Answer 2

I implemented the D&D algorithm @Nivas described, with edge cases handled, in Java. See below code and tests.

Code:

import org.apache.log4j.Logger;

import java.util.Collections;
import java.util.List;
import java.util.Random;

public class RotatedListFindPivot {
    private static final Logger logger = Logger.getLogger(RotatedListFindPivot.class);

    /**
     * With a sorted then rotated list, return the pivot (i.e. smallest or largest),
     * depending on if it was ASCENDING or DESCENDING
     * <p>
     * Multiple appearance of the same value is allowed. It will work as defined:
     * return the smallest/largest, or one of the smallest/largest elements
     * <p>
     * In the extreme case where all elements in the list are equal, it returns any element
     *
     * @param list
     * @param sortingOrder
     * @param <E>
     * @return the pivot
     */

    public static <E extends Comparable> E rotatedListFindPivot(List<E> list, Util.SortingOrder sortingOrder) {
        if (list == null || list.size() == 0) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        /*
        Divide and Conquer. Given a rotated list, pick any element to be mid (the first of right half),
        It holds that only either one half is sorted. If both halves sorted, then left most element is pivot
        */
        int left = 0, right = list.size() - 1;
        /*
        First need to deal with special case: 3,3,3,1,2,3,3,3,3,3,3
        This will seem as if both halves sorted.
        */

        E removedFlatEdge = null;
        if (list.get(left).equals(list.get(right))) {
            removedFlatEdge = list.get(0);
        }
        while (right > left
                && list.get(left).equals(list.get(right))
                && list.get(left).equals(removedFlatEdge)) {
            right--;
            left++;
        }
        if (right < left) {
            return removedFlatEdge;
        }
        E result = rotatedListFindPivotRecur(list, left, right, sortingOrder);
        return removedFlatEdge == null ? result : (removedFlatEdge.compareTo(result) < 0 ? removedFlatEdge : result);
    }

    private static <E extends Comparable> E rotatedListFindPivotRecur(List<E> list, int left, int right, Util.SortingOrder sortingOrder) {
        if (left == right) {
            return list.get(left);
        }

        int mid = left + (int) Math.ceil(((double) right - left) / 2);

        /*
        Both sorted. Is there a rotation (gap)?
         */
        if (list.get(left).compareTo(list.get(mid - 1)) <= 0 && list.get(mid).compareTo(list.get(right)) <= 0) {
            if (list.get(mid - 1).compareTo(list.get(mid)) <= 0) {
                /*
                No gap
                 */
                return list.get(left);
            } else {
                /*
                There is a gap. Mid is pivot
                 */
                return list.get(mid);
            }

        }

        /*
        Left half sorted
         */
        if (list.get(left).compareTo(list.get(mid)) <= 0) {
            return rotatedListFindPivotRecur(list, mid + 1, right, sortingOrder);
        }

        /*
        Right half sorted
         */
        if (list.get(mid).compareTo(list.get(right)) <= 0) {
            return rotatedListFindPivotRecur(list, left, mid - 1, sortingOrder);
        }

        logger.warn("Should never reach here");
        return null;
    }

    public static <E extends Comparable> E rotatedListFindPivotNaive(List<E> list, Util.SortingOrder sortingOrder) {
        if (list == null || list.size() == 0) {
            return null;
        }

        boolean isAscending = sortingOrder == Util.SortingOrder.ASCENDING ? true : false;
        E pivot = list.get(0);
        for (E e : list) {
            if ((e.compareTo(pivot) < 0) == isAscending) {
                pivot = e;
            }
        }

        return pivot;
    }

    public static <E> List<E> rotate(List<E> input) {
        Random random = new Random();
        int rotateBy = random.nextInt(input.size());
        Collections.rotate(input, rotateBy);
        return input;
    }
}

Test:

import org.junit.Test;

import java.util.*;

import static org.junit.Assert.assertEquals;

public class RotatedListFindPivotTest {

    private static final int RANDOM_LIST_LOW = 1;
    private static final int RANDOM_LIST_SIZE = 12;
    private static final int RANDOM_LIST_HIGH = 6;
    private static final int NUM_RANDOM_TESTS = 12000000;

    @Test
    public void testTwoLevelsOfPlateaus() throws Exception {

        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("TwoLevelsOfPlateaus: [3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3]", new Integer(1), result);
    }

    @Test
    public void testRotatedListFindPivotRemovedEdgeIsPivot() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(0, 0, 2, 3, 3, 3, 4, 4, 5, 5, 0, 0)),
                Util.SortingOrder.ASCENDING);
        assertEquals("RemovedEdgeIsPivot: [0, 0, 2, 3, 3, 3, 4, 4, 5, 5, 0, 0]", new Integer(0), result);
    }

    @Test
    public void testRotatedListFindPivotRandomized() throws Exception {

        for (int i=0; i<NUM_RANDOM_TESTS; i++) {
            List<Integer> input = Util.getRandomIntegerList(RANDOM_LIST_SIZE, RANDOM_LIST_LOW, RANDOM_LIST_HIGH);
            Collections.sort(input);
            input = RotatedListFindPivot.rotate(input);
            Integer naiveResult = RotatedListFindPivot.rotatedListFindPivotNaive(input, Util.SortingOrder.ASCENDING);
            Integer result = RotatedListFindPivot.rotatedListFindPivot(input, Util.SortingOrder.ASCENDING);
            assertEquals("Results must hold for inputs: " + input, naiveResult, result);
        }

    }

    @Test
    public void testRotatedListFindPivotTwoSegmentFlatList() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Two Segment flat list should return any from right half, {3,3,1,1}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(3, 3, 3, 1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Two Segment flat list should return any from right half, {3,3,3,1,1}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(3, 3, 1, 1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Two Segment flat list should return any from right half, {3,3,1,1,1}", new Integer(1), result);
    }

    @Test
    public void testRotatedListFindPivotSingletonList() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                Collections.singletonList(1),
                Util.SortingOrder.ASCENDING);
        assertEquals("Singleton list should return the elem, {1}", new Integer(1), result);
    }

    @Test
    public void testRotatedListFindPivotSimpleFlatList() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Total flat list should return any elem, {1,1,1}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(1, 1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Total flat list should return any elem, {1,1,1}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(1, 1, 1, 1)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Total flat list should return any elem, {1,1,1,1}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(2, 1, 2, 2)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple flat list should work, {2,1,2,2}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(2, 2, 1, 2)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple flat list should work, {2,2,1,2}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(2, 1, 2)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple flat list should work, {2,1,2}", new Integer(1), result);
    }

    @Test
    public void testRotatedListFindPivotEmptyList() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(),
                Util.SortingOrder.ASCENDING);
        assertEquals("Empty list should return null", null, result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                null,
                Util.SortingOrder.ASCENDING);
        assertEquals("Null list should return null", null, result);
    }

    @Test
    public void testRotatedListFindPivotSimpleCase() throws Exception {
        Integer result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(1, 2, 3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Not rotated should return pivot, {1,2,3,4}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(4,1,2,3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple case should hold, {4,1,2,3}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(4,1,2,3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple case should hold, {3,4,1,2}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(4,1,2,3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple case should hold, {3,4,1,2}", new Integer(1), result);

        result = RotatedListFindPivot.rotatedListFindPivot(
                new ArrayList<Integer>(Arrays.asList(4,1,2,3)),
                Util.SortingOrder.ASCENDING);
        assertEquals("Simple case should hold, {2,3,4,1}", new Integer(1), result);
    }
}