When finding the largest or smallest element of a list, do we always have to check every value?

Question

In the context of this code challenge, when finding the largest or smallest element of a list, do we always have to check every value?

Answer

This will depend on whether the list is sorted or unsorted.

If the list is unsorted, then yes, you would have to go through every value of the list. This is because we can never be sure if the unchecked values might be the largest or smallest value of the list, as they can appear in any order. So to be certain, we must have checked every single value of the list.

If the list is sorted, then no, we do not have to check every value. We would actually only need to check the first and last elements of the list. This works for lists sorted in ascending or descending order, and would always give us the smallest and largest elements of the list.

8 Likes

12 posts were merged into an existing topic: Can I solve this problem using sort or sorted?

This is my code. Is there anything that can be improved?

#Write your function here
def max_num(nums):
  while len(nums) > 1:
    if nums[0] >= nums[-1]:
      nums.pop()
    else:
      nums.pop(0)
  return nums[0]

#Uncomment the line below when your function is done
print(max_num([50, -10, 0, 75, 20]))
1 Like

can this be improved?

Yes, very likely since it has a ubiquitous flaw, list.index(). This will only find the first of possibly two or more duplicate values.

The solution should not require a nested loop, either. That would make it a quadratic, rather than linear solution. We are told that any solution for this will be at worst, O(N), which means one iteration of the list.

is this a better way?

Still using the index method which is only useful if we are certain there are no duplicates in the list.

 array = [2,3,4,5,2,3,4,5,2,3,4,5]
 array.index(4)    =>  2

and it will always be 2 even if the 4 we are examining is at index[10].

You have a variable to hold the biggest value, which is important. When we iterate the list, we only need to replace that value if the current value is greater.

if num > biggest_number:
    biggest_number = num

Aside

When there is a need to know both index and value, reach for the enumerate() function. It will always return the actual index of the current value. It is not needed in this problem, though.

Say we wish to know both the largest number and its position in the list:

# initialize
i, n = 0, array[0]
for k, x in enumerate(array):
if x > n:
    n = x
    i = k
return k, n

The return will be a tuple containing the index and value, respectively.

idx, max = max_num([2,3,4,5,2,3,4,5,2,3,4,5])
print (max)  =>  5
print (idx)  =>  3

Note that if we use >=, we will get the last index.

print (max)  =>  5
print (idx)  =>  11
1 Like

okay so i under stand the whole problem with me using index, so for this exercise would this actually work now?

def max_num(lst):
    biggest_number = 0
    for nums in range(len(lst)):
        if nums == 0:
            biggest_number = lst[nums]
        elif lst[nums] > biggest_number:
            biggest_number = lst[nums]
    return biggest_number


print(max_num([50, -10, 0, 75, 20]))

and thanks for the help i appreciate it!

1 Like

The best place to start is at the first element in the list. Don’t use 0 since the list could contain all negative numbers. Use lst[0] instead.

There is no need to complicate the if statement. A simple if and an action is all that is needed.

def max_num(lst):
    biggest_number = lst[0]
    for nums in range(len(lst)):
        if lst[nums] > biggest_number:
            biggest_number = lst[nums]
    return biggest_number


print(max_num([50, -10, 0, 75, 20]))

That will work, but since we don’t need the index, you could just iterate over the values.

 for num in lst:

why does the solution have maximum = nums [0] when i got the correct answer with maximum = nums?

My solution with correct answer:

def max_num(nums):
maximum = nums
for number in nums:
if number > maximum:
maximum = number
return maximum

Codecademy solution:

def max_num(nums):
maximum = nums[0]
for number in nums:
if number > maximum:
maximum = number
return maximum

Considering that nums is a list, all that line does is create a second reference to the same data structure.

if number > maximum

That line is comparing a number to a list, as a consequence of maximum being a reference to a list.

The CC solution takes the number at the start of list and assigns it to maximum.