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

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.

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

• Hi I've edited my post with my code. This is also not for a programming competition but was an activity given a month ago given to us by our professor in our university. It was exceeding the time limit and I can't make it more efficient. I want to learn to make my code more efficient as we have an upcoming coding exam which are algorithmic in nature according to him. Mar 23 at 12:27
• First, critically, the description is inaccurate because this is not an O(n^2) algorithm. for; for; max means O(n^3). Mar 23 at 12:36
• Oops, i'm fairly new to big O notation so sorry for the misinformation. Mar 23 at 12:47
• It's OK. Essentially, the max() implies a third hidden for loop contained in the Python runtime's own code. Mar 23 at 12:50
• People are more likely to answer this if you better clarify the problem. Please take an example input and explain in English what it needs to do to product an output. Also, in your examples, it's not clear what is input and what is output. Mar 23 at 13:08

# 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().

• I don't think PEP-8 is correct, here. n is usually used for a single int, whereas N suggests a list of int in mathematics. You'd usually write something like ns – or, I suppose, h. Mar 24 at 20:10
• PEP-8 is by definition correct; it is not held accountable to e.g. the AMS. However yes, I take your point. I understand the centuries long tradition and routinely bite my tongue on code reviews which involve an explicit citation to mathematical material which employs such notation. In this particular case the python code is less helpful than it could be. A plural container name would help. I reject nums as vague. I considered proposing heights but bit my tongue so as not to muddy the waters.
– J_H
Mar 24 at 20:22
• PEP-8 is only correct because it contains a passage: “However, know when to be inconsistent – sometimes style guide recommendations just aren’t applicable. When in doubt, use your best judgment. Look at other examples and decide what looks best. And don’t hesitate to ask!” That said: I see no reason not to spend a few paragraphs explaining your thoughts on naming conventions, even if you end up giving five or six different suggestions. The two sentences you've got right now don't explain anything, so aren't that helpful (except to people who don't need advice). Mar 24 at 20:26
• I am happy to explain myself. Many remarks arise when reading code, related to "why is this hard to understand? how could the author have aided my rapid comprehension?" I write down a subset of them, with the goals of (1.) improving the code artifact in front of us prior to merging it down to main, and (2.) improving code the author shall write in future, that is, I'm trying to teach. You have to "pick your battles", since no codebase will ever be perfect, and I try to meet each author where they are. Here, I believed the author hadn't read PEP-8, and should.
– J_H
Mar 24 at 20:33

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.

• Hello, I made my post clearer! I modified the problem. Pleade let me know if you need any more clarifications. Mar 23 at 13:45

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

• I'm unclear on how this is O(n). Surely the for/while exceeds O(n). Mar 24 at 23:31
• @Reinderien Every element enters and leaves the stack at most once, hence the sum of the number of iterations of the inner while loop is O(n). Mar 24 at 23:49

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))

• I think this is still O(n^2) in the worst case, as if the buildings all have the same height your loops will never break before going through each building.
– Leo
Mar 24 at 2:46
• Actually, your solution as written may be incorrect for buildings with the same height. You need to use >= rather than > to compare heights
– Leo
Mar 24 at 3:00
• You need to indent the code in the 1st code block properly. Mar 24 at 10:39
• Welcome to Code Review! it appears you have a registered for an account twice (as evidenced by the suggested edit), and those two can be merged. You can use the contact SE page near the end of the page and request the accounts be merged. Mar 25 at 15:18