Mark As Completed Discussion

Good afternoon! Here's our prompt for today.

We're given an array of integers that looks like the following:

JAVASCRIPT
1[0, 1, 2, 3, 4, 5, 6, 7, 8]

Let's imagine we're an assembly line and we decide to shift some workers around.

Say we take our array, and rotate it at a random pivot so that the section after the pivot comes before. Let's put our pivot between 5 and 6:

JAVASCRIPT
1[6, 7, 8, 0, 1, 2, 3, 4, 5]

See how it shifts?

Description

Can you find the smallest element in O(log n) time? Assume that there are no repeat numbers.

Here are some other examples: given [4, 5, 1, 2, 3], we'd get 1.

In the event that there's a missing number in the sequence like [5, 6, 7, 0, 1, 2, 3] (where 4 isn't present), the output would still be 0.

Constraints

  • Length of the array <= 100000
  • The values in the array will be between -1000000000 and 1000000000
  • Expected time complexity : O(log n)
  • Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.