ARRAY

1. Reverse the array

# Original list
arr = [1, 2, 3, 4, 5]

# Reverse the list using slicing

reversed_arr = arr[::-1]

print(reversed_arr) # Output: [5, 4, 3, 2, 1]

2. Min & max array

def find_min(arr):
if not arr:
raise ValueError("List is empty")
min_val = arr[0]
for item in arr:
if item < min_val:
min_val = item
return min_val

def find_max(arr):
if not arr:
raise ValueError("List is empty")
max_val = arr[0]
for item in arr:
if item > max_val:
max_val = item
return max_val

# Example usage
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

print(f"Minimum value: {find_min(arr)}") # Output: Minimum value: 1

print(f"Maximum value: {find_max(arr)}") # Output: Maximum value: 9

3. Find the "Kth" max and min element of an array

# Example list
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# Define the value of k

k=3
try:
kth_min = find_kth_min(arr, k)
kth_max = find_kth_max(arr, k)

print(f"The {k}-th minimum value: {kth_min}") # Output: The 3-th minimum value: 3
print(f"The {k}-th maximum value: {kth_max}") # Output: The 3-th maximum value: 5
except ValueError as e:
print(e)

Given an array which consists of only 0, 1 and 2. Sort the array

4.

without using any sorting algo

def sort_012(arr):
"""
Sort an array consisting of 0s, 1s, and 2s using the Dutch National Flag algorithm.

Args:
arr (list): The list containing only 0s, 1s, and 2s.

Returns:
None: The list is sorted in place.
"""
low = 0
mid = 0
high = len(arr) - 1

while mid <= high:

if arr[mid] == 0:
# Swap arr[low] and arr[mid], increment both pointers
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
# Just move the mid pointer
mid += 1
else: # arr[mid] == 2
# Swap arr[mid] and arr[high], decrement high pointer
arr[high], arr[mid] = arr[mid], arr[high]
high -= 1

# Example usage
arr = [2, 0, 1, 2, 0, 1, 0]
sort_012(arr)
print(arr) # Output: [0, 0, 0, 1, 1, 2, 2]
5.Move all the negative elements to one side of the array
. # Python code for the same approach
def move(arr):
arr.sort()

# driver code
arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ]
move(arr)
for e in arr:
print(e , end = " ")

# This code is contributed by shinjanpatra

6. def find_union_and_intersection(arr1, arr2):

"""
Find the union and intersection of two sorted arrays.

Args:
arr1 (list): The first sorted list.
arr2 (list): The second sorted list.

Returns:
tuple: A tuple containing two lists: (union, intersection).
"""
union = []
intersection = []

i=0
j=0

# Traverse both arrays

while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
union.append(arr1[i])
i += 1
elif arr1[i] > arr2[j]:
union.append(arr2[j])
j += 1
else:
# Both are equal
union.append(arr1[i])
intersection.append(arr1[i])
i += 1
j += 1

# Add remaining elements from arr1

while i < len(arr1):
 union.append(arr1[i])
i += 1

# Add remaining elements from arr2

while j < len(arr2):
union.append(arr2[j])
j += 1

return union, intersection

# Example usage
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]

union, intersection = find_union_and_intersection(arr1, arr2)

print("Union:", union) # Output: Union: [1, 2, 3, 4, 5, 6, 7]

print("Intersection:", intersection) # Output: Intersection: [2, 5]

7.def rotate_array_by_one(arr):
"""
Cyclically rotates an array by one position to the right.
Args:
arr (list): The list of elements to rotate.

Returns:
None: The array is rotated in place.
"""
if len(arr) <= 1:
return # No rotation needed for empty or single-element arrays

last_element = arr[-1] # Store the last element

# Shift all elements one position to the right
for i in range(len(arr) - 1, 0, -1):
arr[i] = arr[i - 1]
# Place the last element at the first position
arr[0] = last_element

# Example usage
arr = [1, 2, 3, 4, 5]
rotate_array_by_one(arr)
print(arr) # Output: [5, 1, 2, 3, 4]
8. def max_subarray_sum(arr):
"""
Finds the largest sum of a contiguous subarray using Kadane's Algorithm.
Args:
arr (list): The list of integers.

Returns:
int: The largest sum of the contiguous subarray.
"""
if not arr:
return 0 # Handle edge case where the list is empty

max_current = max_global = arr[0]

for num in arr[1:]:

max_current = max(num, max_current + num)
if max_current > max_global:
max_global = max_current

return max_global

# Example usage
arr = [1, -2, 3, 4, -1, 2, 1, -5, 4]
result = max_subarray_sum(arr)
print("The largest sum of the contiguous subarray is:", result) # Output: 10

9.def minimize_max_diff(heights, k):

# Sort the array to make it easier to calculate the min/max after modification
heights.sort()
# Initialize result as the current difference between the max and min heights
n = len(heights)
if n == 1:
return 0 # If there is only one height, no need to minimize anything

max_diff = heights[-1] - heights[0]

# Consider both ends after modification

small = heights[0] + k
big = heights[-1] - k

# Swap if needed to ensure small is less than big

if small > big:
small, big = big, small
 # Traverse the heights array and update the max and min
for i in range(1, n-1):
subtract = heights[i] - k
add = heights[i] + k

# If the modification doesn't affect the range, skip this element

if subtract >= small or add <= big:
continue

# Update the small or big accordingly

if big - subtract <= add - small:
small = subtract
else:
big = add

return min(max_diff, big - small)

# Example usage:
heights = [1, 15, 10]
k=6
result = minimize_max_diff(heights, k)
print(f"The minimized maximum difference is: {result}")

10. Minimum no. of Jumps to reach end of an array

def min_jumps(arr):
n = len(arr)

# If array has only one element or cannot move forward

if n == 1:
return 0
if arr[0] == 0:
return -1

# Initialize maximum reach, steps and jumps

max_reach = arr[0]
step = arr[0]
jumps = 1

for i in range(1, n):

# If we reached the end of the array
if i == n - 1:
return jumps
 # Update the maximum reach
max_reach = max(max_reach, i + arr[i])

# Use a step to move forward

step -= 1

# If no steps are remaining

if step == 0:
# We need to jump
jumps += 1

# If current index is greater than or equal to the max reachable point, return -1
if i >= max_reach:
return -1

# Reinitialize steps
step = max_reach - i

return -1 # If we never reached the end

# Example usage:
arr = [2, 3, 1, 1, 2, 4, 2, 0, 1, 1]
result = min_jumps(arr)
print(f"Minimum number of jumps to reach the end: {result}")

11. def find_duplicate(nums):

# Phase 1: Using Floyd's Tortoise and Hare (Cycle Detection)
slow = nums[0]
fast = nums[0]

# Move slow by 1 step and fast by 2 steps until they meet

while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break

# Phase 2: Find the entrance to the cycle (which is the duplicate)

slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]

return slow

# Example usage:
nums = [3, 1, 3, 4, 2]
result

12. Merge 2 sorted arrays without using Extra space.

def next_gap(gap):
if gap <= 1:
return 0
return (gap // 2) + (gap % 2)

def merge(arr1, arr2, n, m):

gap = n + m # Initialize the gap as the total number of elements

gap = next_gap(gap) # Find the initial gap

while gap > 0:
# First, compare elements in arr1
i=0
while i + gap < n:
if arr1[i] > arr1[i + gap]:
arr1[i], arr1[i + gap] = arr1[i + gap], arr1[i] # Swap
i += 1

# Now, compare elements between arr1 and arr2

j = gap - n if gap > n else 0
while i < n and j < m:
if arr1[i] > arr2[j]:
arr1[i], arr2[j] = arr2[j], arr1[i] # Swap
i += 1
j += 1

# Lastly, compare elements in arr2

if j < m:
j=0
while j + gap < m:
if arr2[j] > arr2[j + gap]:
arr2[j], arr2[j + gap] = arr2[j + gap], arr2[j] # Swap
j += 1

# Reduce the gap for the next iteration

gap = next_gap(gap)

# Example usage:
arr1 = [1, 4, 7, 8, 10]
arr2 = [2, 3, 9]
n = len(arr1)
m = len(arr2)
merge(arr1, arr2, n, m)
print("Merged arr1:", arr1)
print("Merged arr2:", arr2)

13. Kadane's Algo [V.V.V.V.V IMP]

def kadane(arr):
# Initialize variables
max_current = arr[0] # This will track the current subarray sum
max_global = arr[0] # This will store the global maximum sum

for i in range(1, len(arr)):

# Update max_current by including the current element or starting a new subarray
max_current = max(arr[i], max_current + arr[i])

# Update max_global if max_current is greater

if max_current > max_global:
max_global = max_current

return max_global

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = kadane(arr)
print(f"The maximum subarray sum is: {result}")

14. Merge Intervals

def merge_intervals(intervals):
if not intervals:
return []

# Step 1: Sort the intervals by the start time

intervals.sort(key=lambda x: x[0])

# Step 2: Initialize the result with the first interval

merged = [intervals[0]]

for i in range(1, len(intervals)):

# If the current interval overlaps with the last merged interval, merge them
if intervals[i][0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], intervals[i][1])
 else:
# If not overlapping, add the current interval to the merged list
merged.append(intervals[i])

return merged

# Example usage:
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
result = merge_intervals(intervals)
print(f"Merged Intervals: {result}")

15. Next Permutation

def next_permutation(nums):
# Step 1: Find the first decreasing element from the right
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1

# If no such element is found, the list is sorted in descending order

if i == -1:
nums.reverse()
return nums

# Step 2: Find the next larger element to swap with nums[i]

j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1

# Step 3: Swap the two elements

nums[i], nums[j] = nums[j], nums[i]

# Step 4: Reverse the elements to the right of i

nums[i + 1:] = reversed(nums[i + 1:])

return nums

# Example usage:
nums = [1, 2, 3]
print(next_permutation(nums)) # Output: [1, 3, 2]

16. Count Inversion

def merge_and_count(arr, temp_arr, left, mid, right):

i = left # Starting index for left subarray

j = mid + 1 # Starting index for right subarray

k = left # Starting index to be sorted

inv_count = 0

# Merge the two subarrays

while i <= mid and j <= right:

if arr[i] <= arr[j]:

temp_arr[k] = arr[i]

i += 1

else:

temp_arr[k] = arr[j]

inv_count += (mid-i + 1) # All remaining elements in the left subarray are inversions

j += 1

k += 1

# Copy the remaining elements of the left subarray, if any

while i <= mid:

temp_arr[k] = arr[i]

i += 1

k += 1

# Copy the remaining elements of the right subarray, if any

while j <= right:

 temp_arr[k] = arr[j]

j += 1

k += 1

# Copy the sorted subarray into the original array

for i in range(left, right + 1):

arr[i] = temp_arr[i]

return inv_count

def merge_sort_and_count(arr, temp_arr, left, right):

inv_count = 0

if left < right:

mid = (left + right)//2

inv_count += merge_sort_and_count(arr, temp_arr, left, mid)

inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)

inv_count += merge_and_count(arr, temp_arr, left, mid, right)

return inv_count

def count_inversions(arr):

temp_arr = [0]*len(arr)
 return merge_sort_and_count(arr, temp_arr, 0, len(arr)-1)

# Example usage

arr = [1, 20, 6, 4, 5]

print(f"Number of inversions are {count_inversions(arr)}")

17. def max_profit(prices):

if not prices:

return 0

min_price = float('inf') # Initialize the minimum price as infinity

max_profit = 0 # Initialize maximum profit

for price in prices:

if price < min_price:

min_price = price # Update minimum price

elif price - min_price > max_profit:

max_profit = price - min_price # Update maximum profit

return max_profit

# Example usage

prices = [7, 1, 5, 3, 6, 4]

print(f"Maximum profit: {max_profit(prices)}")

19. def find_pairs(arr, target_sum):

seen = set() # Set to store numbers we have seen

pairs = [] # List to store the result pairs

for num in arr:

# Calculate the number needed to form the target sum

complement = target_sum - num

# If the complement exists in the set, we found a pair

if complement in seen:

pairs.append((complement, num))

# Add the current number to the set

seen.add(num)

return pairs

# Example usage

arr = [1, 5, 7, -1, 5]

target_sum = 6

result = find_pairs(arr, target_sum)

print(f"Pairs with sum {target_sum}: {result}")

20. def find_common_elements(arr1, arr2, arr3):

 i, j, k = 0, 0, 0 # Initialize pointers for arr1, arr2, and arr3

common_elements = []

# Traverse all three arrays while elements are left in all of them

while i < len(arr1) and j < len(arr2) and k < len(arr3):

# If all three elements are equal, add it to the result and move all pointers

if arr1[i] == arr2[j] == arr3[k]:

common_elements.append(arr1[i])

i += 1

j += 1

k += 1

# Move the pointer in the array with the smallest element

elif arr1[i] < arr2[j]:

i += 1

elif arr2[j] < arr3[k]:

j += 1

else:

k += 1

return common_elements

# Example usage

arr1 = [1, 5, 10, 20, 40, 80]

arr2 = [6, 7, 20, 80, 100]

arr3 = [3, 4, 15, 20, 30, 70, 80, 120]

result = find_common_elements(arr1, arr2, arr3)

print(f"Common elements: {result}")

21. def rearrange_alternate(arr):

n = len(arr)

# Step 1: Partition the array to move negative numbers to the left side and positive numbers
to the right side

i = -1 # Index of last negative number

for j in range(n):

if arr[j] < 0:

i += 1

arr[i], arr[j] = arr[j], arr[i] # Swap negative number to the left side

# Now, all negative numbers are on the left and positive numbers are on the right

pos = i + 1 # Index of first positive number

neg = 0 # Index of first negative number

# Step 2: Swap alternately

while pos < n and neg < pos and arr[neg] < 0:

# Swap negative and positive numbers

arr[neg], arr[pos] = arr[pos], arr[neg]

pos += 1
 neg += 2 # Move the negative index by 2 to maintain alternating order

return arr

# Example usage

arr = [1, 2, 3, -4, -1, 4, -6, -9, -10]

result = rearrange_alternate(arr)

print(f"Rearranged array: {result}")

22. def subarray_with_zero_sum(arr):

# Create an empty set to store cumulative sums

cumulative_sum = set()

# Initialize the sum of elements

current_sum = 0

# Traverse through the array

for num in arr:

# Add current element to cumulative sum

current_sum += num

# If current sum is 0 or already exists in the set, we found a subarray with sum 0

if current_sum == 0 or current_sum in cumulative_sum:

return True
 # Add the current sum to the set

cumulative_sum.add(current_sum)

# No subarray with 0 sum was found

return False

# Example usage

arr = [4, 2, -3, 1, 6]

result = subarray_with_zero_sum(arr)

print(f"Subarray with zero sum exists: {result}")

23. def factorial(n):

result = 1

for i in range(2, n + 1):

result *= i

return result

# Example usage

n = 100 # Large number

print(f"Factorial of {n} is: {factorial(n)}")

24. def max_product_subarray(arr):

if not arr:
 return 0

# Initialize variables

max_so_far = min_so_far = result = arr[0]

# Traverse through the array

for num in arr[1:]:

# If current element is negative, swap max and min

if num < 0:

max_so_far, min_so_far = min_so_far, max_so_far

# Update max_so_far and min_so_far

max_so_far = max(num, max_so_far * num)

min_so_far = min(num, min_so_far * num)

# Update result with the maximum product found so far

result = max(result, max_so_far)

return result

# Example usage

arr = [2, 3, -2, 4]

result = max_product_subarray(arr)

print(f"Maximum product subarray: {result}")

25. def longest_consecutive_subsequence(arr):

if not arr:

return 0

# Insert all elements into a set for O(1) lookups

num_set = set(arr)

longest_streak = 0

# Iterate over each number in the array

for num in num_set:

# Check if it's the start of a sequence

if num - 1 not in num_set:

current_num = num

current_streak = 1

# Count the length of the consecutive sequence

while current_num + 1 in num_set:

current_num += 1

current_streak += 1

# Update the maximum streak length

longest_streak = max(longest_streak, current_streak)

 return longest_streak

# Example usage

arr = [100, 4, 200, 1, 3, 2]

result = longest_consecutive_subsequence(arr)

print(f"Length of the longest consecutive subsequence: {result}")

26. def find_elements_appearing_more_than_n_by_k(arr, k):

n = len(arr)

if k <= 1:

return arr # If k is 1 or less, all elements are valid

# Step 1: Find potential candidates

candidates = {}

for num in arr:

if num in candidates:

candidates[num] += 1

elif len(candidates) < k - 1:

candidates[num] = 1

else:

to_remove = []

for key in candidates:

candidates[key] -= 1

if candidates[key] == 0:
 to_remove.append(key)

for key in to_remove:

del candidates[key]

# Step 2: Verify the candidates

candidates = {num: 0 for num in candidates.keys()}

for num in arr:

if num in candidates:

candidates[num] += 1

# Collect all candidates that appear more than n/k times

result = []

for num, count in candidates.items():

if count > n // k:

result.append(num)

return result

# Example usage

arr = [1, 2, 3, 1, 1, 2, 2, 3, 3, 4, 4]

k=3

result = find_elements_appearing_more_than_n_by_k(arr, k)

print(f"Elements appearing more than n/k times: {result}")

27. def max_profit_with_two_transactions(prices):

n = len(prices)

if n == 0:

return 0

# Initialize arrays to store profits

profit_one = [0] * n

profit_two = [0] * n

# Compute maximum profit for one transaction

min_price = prices[0]

for i in range(1, n):

min_price = min(min_price, prices[i])

profit_one[i] = max(profit_one[i - 1], prices[i] - min_price)

# Compute maximum profit for two transactions

max_price = prices[-1]

for i in range(n - 2, -1, -1):

max_price = max(max_price, prices[i])

profit_two[i] = max(profit_two[i + 1], max_price - prices[i])

# Combine results to find the maximum profit with two transactions

max_profit = 0

for i in range(n):
 max_profit = max(max_profit, profit_one[i] + profit_two[i])

return max_profit

# Example usage

prices = [12, 14, 17, 10, 14, 13, 12, 15]

result = max_profit_with_two_transactions(prices)

print(f"Maximum profit with at most two transactions: {result}")

28. def is_subset(arr1, arr2):

# Convert arr1 to a set for O(1) average time complexity for membership checks

set_arr1 = set(arr1)

# Check if all elements of arr2 are present in set_arr1

for element in arr2:

if element not in set_arr1:

return False

return True

# Example usage

arr1 = [11, 1, 13, 21, 3, 7]

arr2 = [11, 3, 7]

result = is_subset(arr1, arr2)

print(f"Array {arr2} is a subset of array {arr1}: {result}")

29. def find_triplets(arr, target_sum):

arr.sort() # Sort the array

n = len(arr)

triplets = []

for i in range(n - 2):

left = i + 1

right = n - 1

while left < right:

current_sum = arr[i] + arr[left] + arr[right]

if current_sum == target_sum:

triplets.append((arr[i], arr[left], arr[right]))

# Move pointers to avoid duplicates

while left < right and arr[left] == arr[left + 1]:

left += 1

while left < right and arr[right] == arr[right - 1]:

right -= 1

left += 1

right -= 1

elif current_sum < target_sum:

left += 1

else:
 right -= 1

return triplets

# Example usage

arr = [1, 2, -1, 0, -2, 1]

target_sum = 0

result = find_triplets(arr, target_sum)

print(f"Triplets that sum to {target_sum}: {result}")

30. def trap(height):

if not height:

return 0

n = len(height)

left_max = [0] * n

right_max = [0] * n

# Fill left_max array

left_max[0] = height[0]

for i in range(1, n):

left_max[i] = max(left_max[i - 1], height[i])

# Fill right_max array

 right_max[n - 1] = height[n - 1]

for i in range(n - 2, -1, -1):

right_max[i] = max(right_max[i + 1], height[i])

# Calculate total water trapped

total_water = 0

for i in range(n):

total_water += min(left_max[i], right_max[i]) - height[i]

return total_water

# Example usage

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

result = trap(height)

print(f"Total trapped water: {result}")

31. def find_min_diff(arr, m):

n = len(arr)

# Edge case: If number of students is more than packets, return -1

if m > n:

return -1

# Sort the array

 arr.sort()

# Initialize the minimum difference

min_diff = float('inf')

# Slide the window of size m across the sorted array

for i in range(n - m + 1):

current_diff = arr[i + m - 1] - arr[i]

min_diff = min(min_diff, current_diff)

return min_diff

# Example usage

arr = [12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50]

m = 7 # Number of students

result = find_min_diff(arr, m)

print(f"Minimum difference is: {result}")

32. def smallest_subarray_with_sum(arr, target_sum):

n = len(arr)

min_length = float('inf')

current_sum = 0

start = 0
 for end in range(n):

current_sum += arr[end]

# Contract the window as long as the current_sum is greater than the target_sum

while current_sum > target_sum:

min_length = min(min_length, end - start + 1)

current_sum -= arr[start]

start += 1

return min_length if min_length != float('inf') else 0

# Example usage

arr = [1, 4, 45, 6, 10, 19]

target_sum = 51

result = smallest_subarray_with_sum(arr, target_sum)

print(f"Length of the smallest subarray with sum greater than {target_sum}: {result}")

33. def three_way_partition(arr, pivot):

low = 0

mid = 0

high = len(arr) - 1

while mid <= high:

if arr[mid] < pivot:

 arr[low], arr[mid] = arr[mid], arr[low]

low += 1

mid += 1

elif arr[mid] == pivot:

mid += 1

else:

arr[high], arr[mid] = arr[mid], arr[high]

high -= 1

# Example usage

arr = [3, 8, 2, 1, 5, 6, 4, 7]

pivot = 5

three_way_partition(arr, pivot)

print(f"Array after three-way partitioning around {pivot}: {arr}")

34. def min_swaps_to_bring_elements_together(arr, K):

n = len(arr)

# Count the number of elements less than or equal to K

count = sum(1 for x in arr if x <= K)

# Find the number of elements greater than K in the initial window of size `count`

current_window = sum(1 for i in range(count) if arr[i] > K)

min_swaps = current_window
 # Slide the window across the array

for i in range(count, n):

if arr[i] > K:

current_window += 1

if arr[i - count] > K:

current_window -= 1

min_swaps = min(min_swaps, current_window)

return min_swaps

# Example usage

arr = [1, 3, 5, 2, 8, 6, 4, 7]

K=5

result = min_swaps_to_bring_elements_together(arr, K)

print(f"Minimum swaps required: {result}")

35. def min_operations_to_make_palindrome(arr):

n = len(arr)

l, r = 0, n - 1

operations = 0

while l < r:
 if arr[l] != arr[r]:

operations += 1

l += 1

r -= 1

return operations

# Example usage

arr = [1, 3, 5, 3, 1]

result = min_operations_to_make_palindrome(arr)

print(f"Minimum operations required: {result}")

36. def find_median_sorted_arrays(A, B):

n = len(A)

# Ensure A is the smaller array

if len(A) > len(B):

A, B = B, A

# Binary search on the smaller array A

low, high = 0, len(A)

while low <= high:

partitionA = (low + high) // 2

 partitionB = (n + n + 1) // 2 - partitionA

maxLeftA = float('-inf') if partitionA == 0 else A[partitionA - 1]

minRightA = float('inf') if partitionA == len(A) else A[partitionA]

maxLeftB = float('-inf') if partitionB == 0 else B[partitionB - 1]

minRightB = float('inf') if partitionB == len(B) else B[partitionB]

if maxLeftA <= minRightB and maxLeftB <= minRightA:

# Correct partition

if (n + n) % 2 == 0:

return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.0

else:

return max(maxLeftA, maxLeftB)

elif maxLeftA > minRightB:

# Too far right on A, move left

high = partitionA - 1

else:

# Too far left on A, move right

low = partitionA + 1

raise ValueError("Input arrays are not sorted or have invalid sizes")

# Example usage
A = [1, 3, 8, 9, 15]

B = [7, 11, 19, 21, 18]

result = find_median_sorted_arrays(A, B)

print(f"Median of the two sorted arrays: {result}")

37. def find_median_sorted_arrays(A, B):

# Ensure A is the smaller array

if len(A) > len(B):

A, B = B, A

m, n = len(A), len(B)

low, high = 0, m

while low <= high:

partitionA = (low + high) // 2

partitionB = (m + n + 1) // 2 - partitionA

maxLeftA = float('-inf') if partitionA == 0 else A[partitionA - 1]

minRightA = float('inf') if partitionA == m else A[partitionA]

maxLeftB = float('-inf') if partitionB == 0 else B[partitionB - 1]

minRightB = float('inf') if partitionB == n else B[partitionB]

if maxLeftA <= minRightB and maxLeftB <= minRightA:

 if (m + n) % 2 == 0:

return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.0

else:

return max(maxLeftA, maxLeftB)

elif maxLeftA > minRightB:

high = partitionA - 1

else:

low = partitionA + 1

raise ValueError("Input arrays are not sorted or have invalid sizes")

# Example usage

A = [1, 3, 8]

B = [7, 9, 10, 11]

result = find_median_sorted_arrays(A, B)

print(f"Median of the two sorted arrays: {result}")

1. def count_set_bits_bitwise(n):

count = 0

while n:

count += n & 1 # Increment count if the least significant bit is 1

n >>= 1 # Right shift the bits of the number

return count

# Example usage

n = 29 # Binary representation: 11101

result = count_set_bits_bitwise(n)

print(f"Number of set bits in {n} using bit manipulation: {result}")

2. def find_two_non_repeating_elements(arr):

# Step 1: XOR all elements

xor_all = 0

for num in arr:

xor_all ^= num

# Step 2: Find a set bit in xor_all (rightmost set bit)

set_bit = xor_all & -xor_all

 # Step 3: Initialize variables to hold the two unique numbers

num1, num2 = 0, 0

# Step 4: Divide elements into two groups and XOR separately

for num in arr:

if num & set_bit:

num1 ^= num

else:

num2 ^= num

return num1, num2

# Example usage

arr = [4, 3, 2, 7, 8, 2, 3, 1]

result = find_two_non_repeating_elements(arr)

print(f"The two non-repeating elements are: {result}")

3. def count_bits_to_flip(A, B):

# Step 1: XOR A and B

xor_result = A ^ B

# Step 2: Count the number of set bits in the XOR result

count = 0

while xor_result:
 count += xor_result & 1 # Increment count if the least significant bit is 1

xor_result >>= 1 # Right shift the bits of the XOR result

return count

# Example usage

A = 29 # Binary: 11101

B = 15 # Binary: 01111

result = count_bits_to_flip(A, B)

print(f"Number of bits to flip to convert {A} to {B}: {result}")

4. def count_set_bits(n):

count = 0

i=0

while (1 << i) <= n:

# Total pairs of bits in the current position

total_pairs = (n + 1) // (1 << (i + 1)) * (1 << i)

# Count of remaining bits in the last incomplete group

remaining_bits = max(0, (n + 1) % (1 << (i + 1)) - (1 << i))

# Add the counts

 count += total_pairs + remaining_bits

i += 1

return count

# Example usage

n=5

result = count_set_bits(n)

print(f"Total number of set bits from 1 to {n}: {result}")

5. def is_power_of_two(n):

# A number is a power of two if it has exactly one bit set and is greater than zero

return n > 0 and (n & (n - 1)) == 0

# Example usage

n = 16

result = is_power_of_two(n)

print(f"{n} is a power of two: {result}")

6. def find_position_of_set_bit(n):

# Check if the number is a power of two

if n <= 0 or (n & (n - 1)) != 0:

raise ValueError("The number does not have exactly one set bit.")
 # Find the position of the only set bit

position = 1

while n > 1:

n >>= 1 # Right shift the number to find the bit position

position += 1

return position

# Example usage

n = 16 # Binary: 00010000

position = find_position_of_set_bit(n)

print(f"The position of the only set bit in {n} is: {position}")

7. def copy_set_bits(src, target, start, end):

# Mask to isolate the bits in the range [start, end]

# Create a mask with 1s in the range [start, end]

all_ones = ~0 # This is -1 in binary (all bits set to 1)

left = all_ones << (end + 1) # Mask for bits left of the range

right = (1 << start) - 1 # Mask for bits right of the range

mask = left | right # Combine masks to isolate the range

# Clear the bits in the target number within the range [start, end]

target_cleared = target & mask

 # Extract bits from the source number

src_bits = (src >> start) & ~(mask >> start)

# Copy the extracted bits to the target number

target_with_bits = target_cleared | (src_bits << start)

return target_with_bits

# Example usage

src = 0b1101 # Source number (binary: 1101)

target = 0b0000 # Target number (binary: 0000)

start = 1 # Starting position of the range (0-based index)

end = 3 # Ending position of the range (0-based index)

result = copy_set_bits(src, target, start, end)

print(f"Target after copying set bits: {bin(result)}")

8. def divide(dividend, divisor):

# Constants for the bounds of integer values

INT_MAX = 2**31 - 1

INT_MIN = -2**31

# Handle special cases

if dividend == 0:
 return 0

if divisor == 0:

raise ValueError("Cannot divide by zero.")

# Determine the sign of the result

negative = (dividend < 0) != (divisor < 0)

# Work with positive numbers for simplicity

dividend, divisor = abs(dividend), abs(divisor)

quotient = 0

power = 31 # Assuming 32-bit integers

# Find the largest power of two multiple of the divisor

while dividend >= divisor:

# Find the highest bit where (divisor << power) is <= dividend

while (divisor << power) > dividend:

power -= 1

# Update dividend and quotient

dividend -= divisor << power

quotient += 1 << power

# Apply the sign to the quotient

 if negative:

quotient = -quotient

# Handle overflow cases

if quotient < INT_MIN:

return INT_MIN

if quotient > INT_MAX:

return INT_MAX

return quotient

# Example usage

dividend = 10

divisor = 3

result = divide(dividend, divisor)

print(f"Result of dividing {dividend} by {divisor} is: {result}")

10. def square_number(n):

# Handle the case where n is negative

if n < 0:

n = -n # Square of a negative number is the same as the square of its positive counterpart

result = 0

odd_number = 1
 # Sum the first n odd numbers

for _ in range(n):

result += odd_number

odd_number += 2

return result

# Example usage

number = 5

result = square_number(number)

print(f"The square of {number} is: {result}")

11. def power_set(nums):

power_set_size = 1 << len(nums) # 2^n

result = []

for i in range(power_set_size):

subset = []

for j in range(len(nums)):

# Check if the j-th bit in i is set

if i & (1 << j):

subset.append(nums[j])

result.append(subset)
 return result

# Example usage

nums = [1, 2, 3]

result = power_set(nums)

print(f"Power set of {nums}: {result}")

1. class TrieNode:
def __init__(self):
self.children = {} # Dictionary to store child nodes
self.is_end_of_word = False # Flag to mark the end of a word
class Trie:
def __init__(self):
self.root = TrieNode() # Initialize the root of the trie

def insert(self, word):

node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode() # Create a new node if it does not exist
node = node.children[char]
node.is_end_of_word = True # Mark the end of the word

def search(self, word):

node = self.root
for char in word:
if char not in node.children:
return False # Word not found
 node = node.children[char]
return node.is_end_of_word # Return True if it is the end of the word

def starts_with(self, prefix):

node = self.root
for char in prefix:
if char not in node.children:
return False # Prefix not found
node = node.children[char]
return True # Return True if the prefix is found

# Example usage
trie = Trie()
trie.insert("hello")
trie.insert("world")

print(trie.search("hello")) # Output: True

print(trie.search("hell")) # Output: False
print(trie.starts_with("hell")) # Output: True
print(trie.starts_with("worl")) # Output: True
print(trie.starts_with("worlds")) # Output: False

2. class TrieNode:
def __init__(self):
self.children = {} # Dictionary to store child nodes
self.count = 0 # Count of how many words pass through this node
class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):

node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
 node.count += 1 # Increment count for each node visited

def find_unique_prefix(self, word):

node = self.root
prefix = ''
for char in word:
prefix += char
node = node.children[char]
if node.count == 1: # Unique prefix found
return prefix
return prefix
def find_shortest_unique_prefixes(words):
trie = Trie()

# Insert all words into the trie

for word in words:
trie.insert(word)

# Find the shortest unique prefix for each word

unique_prefixes = {}
for word in words:
unique_prefixes[word] = trie.find_unique_prefix(word)

return unique_prefixes

# Example usage
words = ["apple", "banana", "appetizer", "bat", "batman"]
unique_prefixes = find_shortest_unique_prefixes(words)
print("Shortest unique prefixes:")
for word, prefix in unique_prefixes.items():
print(f"{word}: {prefix}")

4. class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
 def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def word_break(s, dictionary):
# Build the trie from the dictionary
trie = Trie()
for word in dictionary:
trie.insert(word)

# DP array to check if the string can be segmented

dp = [False] * (len(s) + 1)
dp[0] = True # Empty string is always a valid segmentation

# Iterate over each position in the string

for i in range(1, len(s) + 1):
node = trie.root
# Check all substrings ending at position i
for j in range(i, 0, -1):
if s[j-1] in node.children:
node = node.children[s[j-1]]
if node.is_end_of_word and dp[j-1]:
dp[i] = True
break
else:
break

return dp[len(s)]

# Example usage
dictionary = ["apple", "pie", "applepie"]
s = "applepie"
print(word_break(s, dictionary)) # Output: True

s = "applepieb"
print(word_break(s, dictionary)) # Output: False

6. from collections import defaultdict

def group_anagrams(words):
# Dictionary to store lists of anagrams
anagram_dict = defaultdict(list)

# Group words by their sorted character tuple

for word in words:
sorted_word = ''.join(sorted(word))
anagram_dict[sorted_word].append(word)

# Print all groups of anagrams

for group in anagram_dict.values():
print(group)

# Example usage
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
group_anagrams(words)

7. class PhoneDirectory:
def __init__(self):
self.contacts = {} # Dictionary to store contacts

def add_contact(self, name, phone_number):

"""Add a contact to the directory."""
if name in self.contacts:
print(f"Contact '{name}' already exists. Updating phone number.")
self.contacts[name] = phone_number
print(f"Contact '{name}' added/updated with phone number {phone_number}.")

def remove_contact(self, name):

"""Remove a contact from the directory."""
if name in self.contacts:
del self.contacts[name]
print(f"Contact '{name}' removed.")
else:
 print(f"Contact '{name}' not found.")

def search_contact(self, name):

"""Search for a contact by name."""
if name in self.contacts:
return f"Contact '{name}' found with phone number {self.contacts[name]}."
else:
return f"Contact '{name}' not found."

def list_contacts(self):
"""List all contacts in the directory."""
if self.contacts:
for name, phone_number in self.contacts.items():
print(f"Name: {name}, Phone Number: {phone_number}")
else:
print("No contacts in the directory.")

# Example usage
directory = PhoneDirectory()
directory.add_contact("Alice", "123-456-7890")
directory.add_contact("Bob", "987-654-3210")
print(directory.search_contact("Alice"))
print(directory.search_contact("Charlie"))
directory.list_contacts()
directory.remove_contact("Alice")
directory.list_contacts()

8. def print_unique_rows(matrix):
unique_rows = set()

# Iterate through each row in the matrix

for row in matrix:
# Convert the row to a tuple (for immutability and hashing)
row_tuple = tuple(row)
if row_tuple not in unique_rows:
# Add the row to the set and print it
unique_rows.add(row_tuple)
 print(row)

# Example usage
matrix = [
[1, 0, 1],
[0, 1, 0],
[1, 0, 1],
[0, 1, 0],
[1, 1, 0]
]

print("Unique rows in the matrix:")

print_unique_rows(matrix)

1. class MinHeap:
def __init__(self):
self.heap = []

def parent(self, i):

return (i - 1) // 2

def left_child(self, i):

return 2 * i + 1

def right_child(self, i):

return 2 * i + 2

def min_heapify(self, i):

smallest = i
left = self.left_child(i)
right = self.right_child(i)

if left < len(self.heap) and self.heap[left] < self.heap[smallest]:

 smallest = left

if right < len(self.heap) and self.heap[right] < self.heap[smallest]:

smallest = right

if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
self.min_heapify(smallest)

def insert(self, key):

self.heap.append(key)
index = len(self.heap) - 1
while index > 0 and self.heap[self.parent(index)] > self.heap[index]:
self.heap[self.parent(index)], self.heap[index] = self.heap[index],
self.heap[self.parent(index)]
index = self.parent(index)

def extract_min(self):
if len(self.heap) < 1:
return None
min_item = self.heap[0]
self.heap[0] = self.heap.pop()
self.min_heapify(0)
return min_item

def build_min_heap(self):
for i in range(len(self.heap) // 2 - 1, -1, -1):
self.min_heapify(i)

def __str__(self):
return str(self.heap)

# Example usage
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(20)
min_heap.insert(5)
min_heap.build_min_heap()
print("Min-Heap:", min_heap)
print("Extract Min:", min_heap.extract_min())
print("Min-Heap after extraction:", min_heap)

2. class MaxHeap:
def __init__(self, array):
self.heap = array
self.build_max_heap()

def parent(self, i):

return (i - 1) // 2

def left_child(self, i):

return 2 * i + 1

def right_child(self, i):

return 2 * i + 2

def max_heapify(self, i, size):

largest = i
left = self.left_child(i)
right = self.right_child(i)

if left < size and self.heap[left] > self.heap[largest]:

largest = left

if right < size and self.heap[right] > self.heap[largest]:

largest = right

if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self.max_heapify(largest, size)

def build_max_heap(self):
for i in range(len(self.heap) // 2 - 1, -1, -1):
self.max_heapify(i, len(self.heap))

def heap_sort(array):
 max_heap = MaxHeap(array)
size = len(max_heap.heap)

for i in range(size - 1, 0, -1):

# Swap the root of the heap with the last element
max_heap.heap[0], max_heap.heap[i] = max_heap.heap[i], max_heap.heap[0]
# Reduce the size of the heap and heapify the root
max_heap.max_heapify(0, i)

return max_heap.heap

# Example usage
array = [4, 10, 3, 5, 1]
sorted_array = heap_sort(array)
print("Sorted Array:", sorted_array)

3. from collections import deque

def max_of_subarrays(arr, k):

if not arr or k <= 0:
return []

n = len(arr)
if k > n:
return []

max_elements = []
dq = deque() # To store indices of array elements

for i in range(n):
# Remove elements outside the current window
if dq and dq[0] == i - k:
dq.popleft()

# Remove elements from the deque that are smaller than the current element
while dq and arr[dq[-1]] < arr[i]:
dq.pop()
 # Add the current element's index to the deque
dq.append(i)

# The maximum of the current window is at the front of the deque

if i >= k - 1:
max_elements.append(arr[dq[0]])

return max_elements

# Example usage
arr = [1, 3, -1, -3, 5, 3, 6, 7]
k=3
print("Maximum of all subarrays of size", k, ":", max_of_subarrays

4. import heapq

def k_largest_elements_heap(arr, k):

if k <= 0 or k > len(arr):
return []

# Build a min-heap of the first k elements

min_heap = arr[:k]
heapq.heapify(min_heap)

for num in arr[k:]:

if num > min_heap[0]:
heapq.heappushpop(min_heap, num)

return sorted(min_heap, reverse=True)

# Example usage
arr = [3, 2, 1, 5, 6, 4]
k=2
print("The", k, "largest elements are:", k_largest_elements_heap(arr, k))

5. import heapq
def kth_smallest_largest_heap(arr, k):
if k <= 0 or k > len(arr):
return None, None

# Min-Heap for k-th largest element

min_heap = []
for num in arr:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heappushpop(min_heap, num)

kth_largest = min_heap[0]

# Max-Heap for k-th smallest element (using negative values for max-heap simulation)
max_heap = []
for num in arr:
if len(max_heap) < k:
heapq.heappush(max_heap, -num)
elif -num > max_heap[0]:
heapq.heappushpop(max_heap, -num)

kth_smallest = -max_heap[0]

return kth_smallest, kth_largest

# Example usage
arr = [3, 2, 1, 5, 6, 4]
k=2
kth_smallest, kth_largest = kth_smallest_largest_heap(arr, k)
print(f"The {k}th smallest element is: {kth_smallest}")
print(f"The {k}th largest element is: {kth_largest}")

6. import heapq

def kth_smallest_largest_heap(arr, k):

if k <= 0 or k > len(arr):
 return None, None

# Min-Heap for k-th largest element

min_heap = []
for num in arr:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heappushpop(min_heap, num)

kth_largest = min_heap[0]

# Max-Heap for k-th smallest element (using negative values for max-heap simulation)
max_heap = []
for num in arr:
if len(max_heap) < k:
heapq.heappush(max_heap, -num)
elif -num > max_heap[0]:
heapq.heappushpop(max_heap, -num)

kth_smallest = -max_heap[0]

return kth_smallest, kth_largest

# Example usage
arr = [3, 2, 1, 5, 6, 4]
k=2
kth_smallest, kth_largest = kth_smallest_largest_heap(arr, k)
print(f"The {k}th smallest element is: {kth_smallest}")
print(f"The {k}th largest element is: {kth_largest}")

7. import heapq

class ListNode:
def __init__(self, value=0, next=None):
 self.value = value
self.next = next

def __lt__(self, other):

return self.value < other.value

def merge_k_sorted_linked_lists(lists):
if not lists:
return None

min_heap = []

# Initialize the heap with the head of each linked list

for i, node in enumerate(lists):
if node:
heapq.heappush(min_heap, (node.value, i, node))

# Dummy node to simplify the merging process

dummy = ListNode()
current = dummy

while min_heap:
_, index, node = heapq.heappop(min_heap)
current.next = node
current = current.next

# If there is a next node in the same list, add it to the heap

if node.next:
heapq.heappush(min_heap, (node.next.value, index, node.next))

return dummy.next

# Helper function to create a linked list from a list of values

def create_linked_list(values):
if not values:
return None
head = ListNode(values[0])
current = head
for value in values[1:]:
 current.next = ListNode(value)
current = current.next
return head

# Helper function to print a linked list

def print_linked_list(head):
current = head
while current:
print(current.value, end=" -> " if current.next else "\n")
current = current.next

# Example usage
lists = [
create_linked_list([1, 4, 5]),
create_linked_list([1, 3, 4]),
create_linked_list([2, 6])
]

merged_head = merge_k_sorted_linked_lists(lists)
print("Merged linked list:")
print_linked_list(merged_head)

8.