Binary Search
arr = [10, 3, 5, 7]
target = 3
# Store original indices with values
indexed_arr = list(enumerate(arr)) # [(0, 10), (1, 3), (2, 5), (3, 7)]
# Sort by value
indexed_arr.sort(key=lambda x: x[1]) # [(1, 3), (2, 5), (3, 7), (0, 10)]
def binary_search_with_original_index(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid][1] == target:
return arr[mid][0] # Return original index
elif arr[mid][1] < target:
left = mid + 1
else:
right = mid - 1
return -1
print("Original index of 3:", binary_search_with_original_index(indexed_arr, 3))
Output
Original index of 3: 1
Two-, Three-, or Four-Pointer Sum and So On
Two pointer sum
arr = [10, 3, 5, 7]target = 8
arr.sort()
def has_two_elements_with_sum(arr, target):
left = 0
right = len(arr) - 1
for i in range(len(arr)-1):
while left < right:
sum = arr[left] + arr[right]
if sum == target:
return True
elif sum < target:
left += 1
else:
right -= 1
return False
print(has_two_elements_with_sum(arr, 8))
Output
Three Pointer Sum
target = 15
arr.sort()
def has_three_elements_with_sum(arr, target):
for i in range(len(arr)-2):
a = arr[i]
left = i + 1
right = len(arr) - 1
while left < right:
sum = a + arr[left] + arr[right]
if sum == target:
return True
elif sum < target:
left += 1
else:
right -= 1
return False
print(has_three_elements_with_sum(arr, 15))
Output
TrueSliding Window: Check if any contiguous subarray of length 2, 3, and 4 sums to target
subarray of length 2 (check if any two numbers sum to target)
def has_pair_with_sum(nums, k, target):
window_sum = sum(nums[:k])
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
if window_sum == target:
return True
return False
arr = [1,2,3,4,5];
print("has subarray sum (for k=2):", has_pair_with_sum(arr, 2, 7))
output
subarray of length 3 (check if any three numbers sum to target)
def has_pair_with_sum(nums, k, target):
window_sum = sum(nums[:k])
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
if window_sum == target:
return True
return False
arr = [1,2,3,4,5];
print("has subarray sum (for k=3):", has_pair_with_sum(arr, 3, 9))
Output
subarray of length 4 (check if any four numbers sum to target)
def has_subarray_with_sum(nums, k, target):
window_sum = sum(nums[:k])
if window_sum == target:
return True
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
if window_sum == target:
return True
return False
# Test case
arr = [1, 2, 3, 4, 5]
k = 4
target = 10
print(f"Has subarray of length {k} with sum {target}:", has_subarray_with_sum(arr, k, target))
Output
Another Code (using non-contiguous k-elements sum)
from itertools import combinations
def has_k_elements_sum(nums, k, target):
for combo in combinations(nums, k):
if sum(combo) == target:
print(f"Found combination: {combo}")
return True
return False
# Example usage:
arr = [1, 2, 3, 4, 5]
k = 3
target = 10
print("Has non-contiguous k-elements sum:", has_k_elements_sum(arr, k, target))
Output
Found combination: (1, 4, 5)
Has non-contiguous k-elements sum: True
Activity Selection Problem using the Greedy algorithm
Schedule the maximum number of non-overlapping events
# Activity Selection Problem using Greedy Algorithm
# Objective: Select the maximum number of non-overlapping activities
# Sample list of activity requests, where each tuple is (start_time, end_time)
activity_requests = [
(1, 3), # Activity 1
(2, 4), # Activity 2
(3, 5), # Activity 3
(0, 6), # Activity 4
(5, 7) # Activity 5
]
# Step 1: Sort the activities by their end time (earliest finishing first)
# Why? Because ending early leaves more room for other activities.
sorted_activities = sorted(activity_requests, key=lambda activity: activity[1])
# Function to select the maximum number of non-overlapping activities
def select_activities_greedily(activities):
selected_activities = [] # List to store selected activities
last_activity_end_time = -1 # Initialize end time tracker
# Step 2: Loop through each sorted activity
for start_time, end_time in activities:
# Step 3: Check if the activity starts after or when the last selected one ended
if start_time >= last_activity_end_time:
selected_activities.append((start_time, end_time)) # Select it
last_activity_end_time = end_time # Update the end time tracker
return selected_activities
# Get the selected non-overlapping activities
optimal_schedule = select_activities_greedily(sorted_activities)
# Print the result
print("Optimal set of non-overlapping activities:")
for i, (start, end) in enumerate(optimal_schedule, 1): # index starts from 1 instead of 0
print(f"Activity {i}: Start = {start}, End = {end}")
Output
Optimal set of non-overlapping activities:
Activity 1: Start = 1, End = 3
Activity 2: Start = 3, End = 5
Activity 3: Start = 5, End = 7
Find the minimum number of meeting rooms required so that no meetings overlap
# Objective: Select the maximum number of non-overlapping activities
# Sample list of activity requests, where each tuple is (start_time, end_time)
activity_requests = [
(0, 30), # Activity 1
(5, 10), # Activity 2
(9, 20) # Activity 3
]
# Step 1: Sort the activities by their end time (earliest finishing first)
# Why? Because ending early leaves more room for other activities.
sorted_activities = sorted(activity_requests, key=lambda activity: activity[1])
# Function to select the maximum number of non-overlapping activities
def select_activities_greedily(activities):
number_of_room = 0 # List to store selected activities
last_activity_end_time = -1 # Initialize end time tracker
# Step 2: Loop through each sorted activity
for start_time, end_time in activities:
# Step 3: Check if the activity starts after or when the last selected one ended
if start_time >= last_activity_end_time:
number_of_room = 1
last_activity_end_time = end_time
else:
number_of_room += 1
return number_of_room
# Get the selected non-overlapping activities
number_of_room = select_activities_greedily(sorted_activities)
# Print the result
print(f"Total number of room required: {number_of_room}")