Skip to content
Open
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Original file line number Diff line number Diff line change
Expand Up @@ -12,20 +12,20 @@ def calculate_sum_and_product(input_numbers: List[int]) -> Dict[str, int]:
"sum": 10, // 2 + 3 + 5
"product": 30 // 2 * 3 * 5
}
Time Complexity:
Space Complexity:
Time Complexity: O(n) because we are iterating through the list once now instead of twice before
Space Complexity: O(1) because we are using a constant amount of space
Optimal time complexity:
We can calculate the sum and the product in a single pass through the list
"""
# Edge case: empty list
if not input_numbers:
return {"sum": 0, "product": 1}

sum = 0
for current_number in input_numbers:
sum += current_number

total = 0
product = 1

for current_number in input_numbers:
product *= current_number
total += current_number

return {"sum": sum, "product": product}
return {"sum": total, "product": product}
31 changes: 22 additions & 9 deletions Sprint-1/Python/find_common_items/find_common_items.py
Original file line number Diff line number Diff line change
Expand Up @@ -9,13 +9,26 @@ def find_common_items(
"""
Find common items between two arrays.

Time Complexity:
Space Complexity:
Optimal time complexity:
Time Complexity:O(n*m*k) because we are iterating through both lists and then checking if the item is already in the common items list
Space Complexity:O(n) because we are storing the common items in a new list
Optimal time complexity: O(n+m) because we have to iterate through both lists at least once to find the common items
"""
common_items: List[ItemType] = []
for i in first_sequence:
for j in second_sequence:
if i == j and i not in common_items:
common_items.append(i)
return common_items
# common_items: List[ItemType] = []
# for i in first_sequence:
# for j in second_sequence:
# if i == j and i not in common_items:
# common_items.append(i)
# return common_items


first_set = set(first_sequence)
second_set = set(second_sequence)
return list(first_set & second_set)

"""
Time Complexity now: O(n+m) because we are iterating through both list once
Space Complexity now: O(n+m) because we are storing the common items in a new list and we are also creating two sets which take up space
Optimal time complexity: O(n+m) because we have to iterate through both lists at least once to find the common items
"""


24 changes: 17 additions & 7 deletions Sprint-1/Python/has_pair_with_sum/has_pair_with_sum.py
Original file line number Diff line number Diff line change
Expand Up @@ -7,12 +7,22 @@ def has_pair_with_sum(numbers: List[Number], target_sum: Number) -> bool:
"""
Find if there is a pair of numbers that sum to a target value.

Time Complexity:
Space Complexity:
Optimal time complexity:
Time Complexity: O(n^2) because we are iterating through the list twice to find the pair of numbers that sum to the target value
Space Complexity: O(1) because we are not using any extra space
Optimal time complexity: O(n) because we can use a hash set to store the numbers we have seen so far
"""
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target_sum:
return True
# for i in range(len(numbers)):
# for j in range(i + 1, len(numbers)):
# if numbers[i] + numbers[j] == target_sum:
# return True
# return False
for num in numbers:
complement = target_sum - num
if complement in numbers:
return True
return False

"""
Time Comlexity now: O(n) because we are iterating once through the list to find the pair
Scape Complexity now: O(n) because we aren't using any extra space, we ca have some list for saving the numbers, but we don't need it here
"""
46 changes: 35 additions & 11 deletions Sprint-1/Python/remove_duplicates/remove_duplicates.py
Original file line number Diff line number Diff line change
Expand Up @@ -4,22 +4,46 @@


def remove_duplicates(values: Sequence[ItemType]) -> List[ItemType]:
# for value in values:
# is_duplicate = False
# for existing in unique_items:
# if value == existing:
# is_duplicate = True
# break
# if not is_duplicate:
# unique_items.append(value)

# return unique_items

"""
Remove duplicate values from a sequence, preserving the order of the first occurrence of each value.

Time complexity:
Space complexity:
Optimal time complexity:
Time complexity: O(n^2) we are iterating for each item in the list and then we're doing another iteration th check duplicates
Space complexity: O(n) creating a new list
Optimal time complexity: O(n) we can use set to check for duplicates
"""
unique_items = []

unique_items: list[ItemType] = []
seen = set()

for value in values:
is_duplicate = False
for existing in unique_items:
if value == existing:
is_duplicate = True
break
if not is_duplicate:
if value not in seen:
seen.add(value)
unique_items.append(value)

return unique_items






# unique_items = list(set(values))

# return unique_items
"""

Time: O(n)
Space: O(n)

"""