Creating an O(n) algorithm for an array of integers

Question

To avoid plagiarism in my university, I am going to modify the problem.

Henry likes to jump from building to building. The heights of each building are given as a list of H numbers. We also number their indices 0,1,…,n−1 from left to right. I want to find out the number of all the buildings that Henry can jump to with these conditions:

Henry can jump from building x to another building y if:

• The building y is not taller than building x
• None of the buildings in between building x and building y are taller than either building x or building y.

For example, if a building x has a height 10, and a building y has a height of 5, and there's a building that has a height of 7 between them, then Henry cannot jump to building y because the building's height in between them is greater than y.

For each building, how many buildings can Henry jump to?
I want it to return as a list.

Here are more examples:

[10, 300, 200] == [0, 2, 0]

Henry cannot jump from building 0 to 1 because 300 > 10. Henry also cannot jump from building 0 to building 2 as building 2 is greater than building 0 and the building in between them is greater than both of them. Henry can jump from building 1 to building 0 and building 2 because building 2 is greater than both of them. Jumping from building 2 to building 1 is not possible as it has a greater height than building 1 and we cannot jump from building 2 to building 0 because the building in between them (building 1) has a height greater than both of them even though building 2 is greater than building 0.

[10000, 1004, 1200] == [2, 0, 1]
[1020, 1020, 1020, 220, 520, 602, 320] == [2, 2, 5, 0, 1, 2, 0]

I've created an O(n^3) solution using two for loops for this solution but it seems highly inefficient. I want to see if there is an O(n log n) solution or an O(n) solution for this one. I am kind of a newbie to programming so something simple could help.

Here is my code:

def valid_jumps(N: list[int]) -> list[int]: validated: list[int] = [] for i in range(len(N)): valid = 0 for j in range(i+1, len(N)): if N[i] >= N[j]: valid += 1 if max(N[i+1:j], default=0) > N[i]: valid -= 1 elif max(N[i+1:j], default=0) > N[j]: valid -= 1 else: break for k in range(i-1, -1, -1): if N[i] >= N[k]: valid += 1 if max(N[k+1:i], default=0) > N[i]: valid -= 1 elif max(N[k+1:i], default=0) > N[k]: valid -= 1 else: break validated.append(valid) return validated 

Another edit: Tried to made my post clearer

Answer 1

lint

def valid_jumps(N: ... 

Pep-8 asks that you spell the parameter name in this way: n

The problem statement suggested referring to it as h.

docstring

It's unclear, from reading the code, how to interpret the input and output vectors. (I do thank you for the helpful type annotations!) Please write an English sentence describing what this function does, and then describe what the input and output values mean. Cite the original problem statement, perhaps via an URL, if that makes it easier to write the docstring.

too long

This function is a mere two dozen lines of source code, and is easily viewed in a single window with no scrolling, so ordinarily we might say that it is Fine as-is.

But it is dense. It is clear the j loop is trying to accomplish a specific goal, and so is the k loop, yet those goals are unnamed. Would you please Extract Helper, twice, and take the opportunity to informatively name those helper functions. Consider giving one or both of them a docstring. Maybe we need just a single helper, which accepts a direction parameter of ±1 ?

The meaning of valid is unclear. It would benefit from a # comment, as typically such a name would correspond to a boolean. Consider renaming to valid_count or num_valid_jumps. Part of the trouble here is that valid is an adjective, yet the problem statement focuses on a certain noun: "jumps".

inner loops

It's unclear why we're asking python's max() to examine lots of heights which turn out to be irrelevant, when bailing out early (for .. break, or while) will save us the work.

Write an appropriate helper so you can express the leftward + rightward jumps problem in this way:

 valid = _jumps(N, i, -1) + _jumps(N, i, 1) 

unit tests

Take a moment to fit the current implementation into a test suite. Now you can easily re-run the tests, verifying Green bar, after each code edit.

Armed with a working cubic implementation, you're in a great position to define some similarly named quadratic implementation, and to verify it computes the identical jump results. Unit tests can make refactors happen quickly.

memoize

Suppose building i is a local maximum, from which Henry can gaze "downhill" rightward for a long distance, all the way to some taller building j. We should be able to exploit that fact when finding valid rightward jumps for i+1, i+2, ..., j-1.

From i we can make j-i-1 jumps. And then we decrement that quantity for each position until we get to j. This suggests that the scalar for i ...: valid = left + right which I proposed above is not a terrific fit for this problem. Prefer to allocate left = [0] * len(N), and similarly for right. Now we can greedily fill in monotonic stretches. At the end we essentially return left + right. That's valid vector notation for numpy, but for list[int] you'll need to write a loop, perhaps as a list comprehension involving zip().

Answer 2

The code layout is good.

It is clear from the code that the function accepts a list of integers and returns a list of integers.

However, you should add a docstring describing more details about the returned list. You could add details for the following:

• It returns a list of the same length as the input list (if that is the case)
• It appears to return a valid indication for each item in the input list. I think of "valid" as being a boolean (1 or 0). What does 2 mean? What does 5 mean?

Essentially, it would be better to more precisely define what you mean by "valid".

DRY

Since your function does not modify the input list N, its length remains the same. However, your code calls len(N) multiple times:

for i in range(len(N)): valid = 0 for j in range(i+1, len(N)): 

Instead, you can set the length to a variable at the top of the function:

nums = len(N) for i in range(nums): valid = 0 for j in range(i+1, nums): 

Similarly for the calls to max:

 if max(N[i+1:j], default=0) > N[i]: valid -= 1 elif max(N[i+1:j], default=0) > N[j]: 

This is simpler:

 max_num = max(N[i+1:j], default=0) if max_num > N[i]: valid -= 1 elif max_num > N[j]: 

Input checking

If the input to your function is known to be good, in other words, if you validate the input before passing it to the function, then ignore the following. Otherwise, consider checking the input in the function. For example, if the input contains a negative value, the output is not what I would expect. Obviously, there is no such thing as a negative height, but you might want to report it to the user. Checking would take some time to do, but it would only be done once for each item in the list.

Answer 3

My approach, n log n:

def valid_jumps_1(N: list[int]) -> list[int]: valid: list[int] = [0] * len(N) for i in range(len(N)): j = i - 1; while j >= 0 and N[i] > N[j]: valid[i] += 1 j -= 1 j = i + 1 while j < len(N) and N[i] > N[j]: valid[i] += 1 j += 1 return valid 

Appears to be n^2 but if you notice the two loops break condition, it evaluates if it has reached one value greater from one side or another. This avoid again looping the entire array and in the best case it breaks the first iteration on the two loops!! for each position in the array.

-You original code benchmark with 35000 random integers (on a laptop 10th gen i5 10210U 4.2GHz): real 1m4,184s user 1m3,965s sys 0m0,010s

• n log n code benchmark with 1000000 random integers (again same pc): real 0m3,312s user 0m3,148s sys 0m0,085s

My test bench code :

import random randomlist = [] for i in range(0,1000000): n = random.randint(1,1000000) randomlist.append(n) print(randomlist) #print(valid_jumps(randomlist)) print(valid_jumps_1(randomlist)) 

Answer 4

This can be solved in O(n) by maintaining a monotonic stack of heights of previous buildings. For each new building, remove all elements from the stack with height not greater than the current element. Any buildings with height less than the current building are reachable from the current building, but not from any other buildings as the current building blocks it. We handle elements with the same height by also keeping track of the frequency of buildings with equal height in the stack.

def valid_jumps(heights: list[int]) -> list[int]: ans = [0] * len(heights) def solve(elems): stk = [] for i, height in elems: tot = same = 0 while stk and stk[-1][0] <= height: curr, freq = stk.pop() if curr == height: same += freq tot += freq ans[i] += tot stk.append((height, same + 1)) solve(enumerate(heights)) solve(reversed(list(enumerate(heights)))) return ans