CODEWITHSUNDEEP
pythonarraysalgorithm
Marcus
Marcus

Reputation: 9472

Find the largest difference - O(n)

I have a coding challenge question that I'm struggling with.

Given an array of integers, iterate through the array (only allowed once) connecting a value with the biggest value to it's right. You are looking for the largest differences.

[1,2,3,6,3,1,4,3,4,2,3]

What would be a possible solution to this problem? I wrote up a solution in python that solves it in longer time. It found the largest difference which in this case would be the 1,2,3 go to [4]. and then recursively do the rest of the list. How would you accomplish this in one iteration of the list?

Upvotes: 0

Views: 183

Answers (1)

abarnert
abarnert

Reputation: 365707

Here's a hint that you should be able to turn into code: walk the list backward.

Think about it this way: The 3 is the largest value to the right of each value, until you hit the 4. Then the 4 is the largest value to the right of each value until you hit the next 6. (If you're supposed to find the leftmost biggest value, as in your sample output, then it's until you hit the next 4, instead.) And so on.

If you can use O(N) temporary space, you can just build up the list of largest values, then reverse it to print out the answers in order. (Or you could do it recursively, which puts the O(N) temporary space on the stack.)

Upvotes: 5

Related Questions