I stumbled upon this problem recently and couldn't solve it on my own. However I know the solution now, and it is a legitimate one (initially I doubted that this would be possible).

You have an array of real numbers in some random order. Devise an algorithm that calculates the biggest difference between adjacent numbers in their sorted order. The algorithm needs to work in linear time, so it's needless to say that sorting the input array is out of the question.

Example:

Input: {2, 1, 100, 102, 8, 5}

Output: 92

(If they were sorted, the biggest difference between adjacent numbers would be between 8 and 100)

Have fun

## A fun problem: Biggest difference between elements

**Moderators:** phlip, Moderators General, Prelates

### A fun problem: Biggest difference between elements

It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

### Re: A fun problem: Biggest difference between elements

I thought of a very simple algorithm

but it fails for arrays like

...so arrays of the form: have a larger gap (A) in front of a smaller gap (B), then have A split into multiple gaps all smaller than B, making it the largest gap.

Since keeping track of all the gaps (e.g. using an ordered data structure, so basically sorting the list) requires at least O(n log n) time, I need to throw more math at the problem.

*space reserved for posterity after more thinking*

**Spoiler:**

but it fails for arrays like

Code: Select all

`[6, 106, 205, 303, 400, 56, 155, 254]`

...so arrays of the form: have a larger gap (A) in front of a smaller gap (B), then have A split into multiple gaps all smaller than B, making it the largest gap.

Since keeping track of all the gaps (e.g. using an ordered data structure, so basically sorting the list) requires at least O(n log n) time, I need to throw more math at the problem.

*space reserved for posterity after more thinking*

- scarecrovv
- It's pronounced 'double u'
**Posts:**674**Joined:**Wed Jul 30, 2008 4:09 pm UTC**Location:**California

### Re: A fun problem: Biggest difference between elements

This might be excessively complicated, but it works.

edit: well it almost works.

**Spoiler:**

edit: well it almost works.

Last edited by scarecrovv on Fri May 01, 2015 3:26 pm UTC, edited 1 time in total.

### Re: A fun problem: Biggest difference between elements

If I understand your algorithm correctly, it fails with the inputs {1, 10, 18, 26} and {1, 12, 22, 23, 25} (or any rearrangements thereof).

**Spoiler:**

- scarecrovv
- It's pronounced 'double u'
**Posts:**674**Joined:**Wed Jul 30, 2008 4:09 pm UTC**Location:**California

### Re: A fun problem: Biggest difference between elements

Nitrodon wrote:If I understand your algorithm correctly, it fails with the inputs {1, 10, 18, 26} and {1, 12, 22, 23, 25} (or any rearrangements thereof).Spoiler:

So it does. Good catch.

edit: Actually due to a bug in my implementation it gets the right answer for your second sequence, but not your first one. Investigating...

edit 2: Here's a fixed version. I've learned my lesson and written a unit test. Also, despite my algorithm theoretically having a better asymptotic time complexity than python's built in sort function, a "naive" implementation actually performs far better in practice on inputs my computer can handle. I'm sure that for sufficiently large inputs my algorithm would win, but my computer can't handle inputs that big.

**Spoiler:**

### Re: A fun problem: Biggest difference between elements

Without reading any of the other posts, I’ve found a solution that uses 2n extra space. It uses that space very inefficiently though, so I expect better is possible:

**Spoiler:**

wee free kings

### Re: A fun problem: Biggest difference between elements

This one is tough, but I think I have a solution:

I've tested this on all the example inputs shown in this thread and it works.

EDIT: So yeah, I have the same algorithm as Scarecrovv and Qaanol. My code is shorter than Scarecrovv's though

**Spoiler:**

I've tested this on all the example inputs shown in this thread and it works.

EDIT: So yeah, I have the same algorithm as Scarecrovv and Qaanol. My code is shorter than Scarecrovv's though

### Re: A fun problem: Biggest difference between elements

On further reflection, it is in fact possible to make do with only n extra space, by cleverly re-using the original array.

wee free kings

### Re: A fun problem: Biggest difference between elements

Qaanol wrote:On further reflection, it is in fact possible to make do with only n extra space, by cleverly re-using the original array.

Yeah, but that's kind of a dick thing to do for a function. Unless you're call-by-value, but who passes an array with call-by-value?

### Re: A fun problem: Biggest difference between elements

Okay fine then, it’s possible with only n extra space and no changes to the array, by making one extra pass over the data.

wee free kings

### Who is online

Users browsing this forum: No registered users and 8 guests