I subscribe to a lovely newsletter that, among other things, presents readers with a coding challenge every week.
I had some fun with last week’s, so I thought I’d do this again, using Rust. So here’s this week’s question:
Given an array that was once sorted in ascending order is rotated at some pivot unknown to you beforehand (so [0,2,4,7,9] might become [7,9,0,2,4], for example). Find the minimum value in that array in O(n) or less.
The way my brain works, this is what jumped at me straight away:
fn find_value_of_drop(arr: &[usize]) -> usize {
// start loop at 1 so we can always look back one space
for i in 1..arr.len() {
// compare this element to the one before, looking for a "drop" in value
if arr[i] < arr[i - 1] {
// if we found a drop, we know this element is the minimum value
return arr[i];
}
}
// If we made it here and still haven't found the drop, we know the array is
// such that the first element is the minimum value, so we'll return that
arr[0]
}
(In fact, I first wrote is as a while loop that ended with a i = i + 1 because even though I haven’t written C++ for 20 years, it’s how I learned loops.)
The trick is that we can find the pivot by finding the first element where the previous element is greater. And once we find the pivot, we have also found the minimum value of the array.
I’m pretty sure that code above works – you can test it yourself against a few tests I wrote.
Using enumerate
After going through this whole thing I realize now that we can use a little Rust to make this a little nicer without disturbing the underlying logic by using enumerate, which I think is similar to Ruby’s “each with index”:
fn find_value_of_drop_more_elegant(arr: &[usize]) -> usize {
for (i, item) in arr.iter().enumerate() {
if let Some(n) = arr.get(i + 1) {
if item > n {
return *n;
}
}
}
arr[0]
}
I like this solution!
But, as I managed to do last week, I wanted to see if there were other, potentially more elegant/Rust-y way to look at this problem. First, I tried cycle, thinking it would help make the problems of (a) running out of elements in the array and (b) checking the first element a bit easier. But I don’t think cycle really helps here.
Peeking
So I looked to peekable / peek, an iterator I think I had tried to use before without success.
I think the fundamental issue for me with these higher level iterators like peek – specifically the ones that return iterators – is that the examples the documentation gives all use next() to move through the example array slice. Here’s the peekable/peek example:
let xs = [1, 2, 3];
let mut iter = xs.iter().peekable();
// peek() lets us see into the future
assert_eq!(iter.peek(), Some(&&1));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
While what I almost always am in need of is a sturdy example that makes use of a loop like for or while. (An exception to this is the nice and concise examples for iterators that return a bool, like all and any, and those that return something other than an iterator, like sum.) How often do I only want to next a couple of times? My only guess is that there’s some general way to loop these specialized iterators.
My instincts (most likely from Ruby, but also from how we used enumerate above) is to want to write something like for (this_element, next_element) in arr.iter().peekable() { and then have access to this_element and an Option of next_element in the block (since if you’re at the end of the array slice you won’t have a next_element). But, of course, this isn’t Ruby.
After some haphazard Googling, I found a forum post (I’ve since lost track of) and adapted to this beast, which passed my tests:
fn find_value_of_drop_more_elegant(arr: &[usize]) -> usize {
let mut peekable_arr = arr.iter().peekable();
while let Some(l) = peekable_arr.next() {
match peekable_arr.peek() {
Some(next_element) => {
if l > next_element {
return **next_element;
}
}
None => return arr[0],
};
}
arr[0]
}
But, phew, at first glance I did not like it, nor did I fully understand it (I still might not).
First of all it’s longer and denser than my first solution (I thought these where supposed to be higher level iterators!). And to me it doesn’t look very approachable or readable, especially at first look, particularly that second line, which uses both a while let and next, a pattern I wasn’t familiar with.
And despite the borrow checker and I reaching some sort of détente about a year ago, that **next_element causes me to raise an eyebrow – usually a sign something is off. I think it’s partially due to peek giving you a reference to the next element (hence the Some(&&1) in the documentation example). And my best guess is that the other * is needed because next() gives references as well, so by that return line it’s like, double referenced?
An attempt at generalizing?
In order to better understand this function that I basically copied from the internet, let’s start slow. Let’s learn about that second line, the one with while let and the dreaded next().
First let’s open the documentation for next() in a browser tab and let it simmer in our minds.
After thinking about next and while let for a bit, I figured out how to write a simplified example without peek or any other high level iterator.
let a = [10, 22, 33, 44, 55, 66];
let mut my_iter = a.iter();
// A call to next() returns the next value as a reference wrapped in
// an Option...
// assert_eq!(Some(&10), my_iter.next());
// And crucially, despite its name, the first time you call it you
// get the FIRST element.
// We should also note that it "returns None when iteration is finished"
// Since we want to loop through all elements, and we're dealing
// with Options, `while let` actually does fit our use-case pretty well!
while let Some(element) = my_iter.next() {
println!("I'm on element {}", element);
}
For me, this shows that this “while-let-next” construction is useful at a pretty low-level, in that we can use it as a way to just iterate (whether we’re doing something fancy like peek or not). Cool!
Next, I knew that while let was a sort of syntatic sugar for avoiding a formal match statement and its None branch – just like if let, which I’ve met before.
I figured “expanding” the while let might help me understand what’s going on better. Looking at the “Rust by Example” explanation of while let, I was able to expand my simplified example out:
let a = [10, 22, 33, 44, 55, 66];
let mut my_iter = a.iter();
loop {
match my_iter.next() {
// if there is indeed a next element... do something
Some(element) => println!("I'm on element {}", element),
// if there's not a next element... break
_ => break, // think this can be None instead of _
}
}
OK cool, cool. Next, the big task: using what I’ve learned with the simpler example and returning to the peekable code. This is where I learned the unfortunate coincidence of the name of the next method, mixed with this coding challenge and peek (which gives you the next next() element, if you get what I mean).
Here’s how I expanded and annotated that while let:
fn find_value_of_drop_using_peek_written_out(vec: &[usize]) -> usize {
// let's set up a super neat peekable iterator
let mut peekable_vec = vec.iter().peekable();
// start an ole fashion loop!
loop {
// this is a crucial line below. We're asking if there are any elements
// left in our peekable array slice. `next()` is a bit of confusing term
// here, because later we'll use peek to look at what you might think of
// as the NEXT element.
match peekable_vec.next() {
// if there is a "next" element...
// call it this_element and see if we can peek ahead to the NEXT element
Some(this_element) => match peekable_vec.peek() {
Some(next_element) => {
// Yes, there is a NEXT element, so we can do our comparison
// because here we have access to both this_element and
// next_element
if this_element > next_element {
return **next_element;
}
}
// No, no NEXT element, so just continue with the loop
// though we could probably break or return vec[0] here...
None => continue,
},
// This means we're really at the end of the vector
// which means the first element is the minimum value
// break so we get to the last line of the function and
// return vec[0]
_ => break,
}
}
vec[0]
}
I think I’m starting to get a handle on it!?
A slightly tighter example using peek and if let
One of the great things about Mastodon is if you toot out some Rust code, someone will refactor it further for you. In this case, my above solution can get significantly tighter (and arguably more readable) by replacing the match statement with an if let. Behold:
fn find_value_of_drop_more_elegant(arr: &[usize]) -> usize {
let mut peekable_arr = arr.iter().peekable();
while let Some(l) = peekable_arr.next() {
if let Some(next_element) = peekable_arr.peek() {
if l > next_element {
return **next_element;
}
}
}
// If we made it here and still haven't found the drop, we know the array is
// such that the first element is the minimum value, so we'll return that
arr[0]
}
Though I think it’s fair to say it’s still quite a bit more formidable than my very first solution (shout-out to high school comp sci!).
Windows
Next to explore is the Rust method windows. Using some of what we learned above from enumerate and peek, I managed to write this out:
fn find_value_of_drop_more_elegant(arr: &[usize]) -> usize {
let mut windows = arr.windows(2);
while let Some(&[this_element, next_element]) = windows.next() {
if this_element > next_element {
return next_element;
}
}
arr[0]
}
Which I think I like better than using peek, right? We get rid of the inner if let at least.
I’m guessing there’s some situation where you could use peek but couldn’t use windows? Maybe if you’re not dealing with a slice? Something to explore.
Thanks to all the Mastodon/Fediverse users who guided me on this far. I’ll leave this a bit open-ended for now: How else can I solve this and learn other Rust methods/iterators? I’m wondering if there’s a one- or two-line solution possible.