- Subarray with Given Sum:
Problem: Find a continuous subarray within a given array that adds up to a specific sum.
Example: For the array [1, 2, 3, 7, 5] and sum 12, the subarray [2, 3, 7] has the sum 12.
Approach: Use the sliding window technique. Start with two pointers at the beginning of the array and expand or contract the window until you find the sum or determine it’s not possible.
def subarray_with_given_sum(arr, target_sum):
start = 0
current_sum = 0
for end in range(len(arr)):
current_sum += arr[end]
while current_sum > target_sum and start <= end:
current_sum -= arr[start]
start += 1
if current_sum == target_sum:
return arr[start:end+1]
return []
# Example usage
arr = [1, 2, 3, 7, 5]
target_sum = 12
print(subarray_with_given_sum(arr, target_sum))- Count the Triplets:
Problem: Count the number of triplets in an array that sum up to a specific value.
Example: For the array [1, 4, 6, 7, 10] and sum 17, the triplets [1, 6, 10] and [7, 10] add up to 17.
Approach: Use nested loops or a hash set to find all possible triplets and count those that match the desired sum.
def count_triplets(arr, target_sum):
count = 0
n = len(arr)
for i in range(n - 2):
seen = set()
current_sum = target_sum - arr[i]
for j in range(i + 1, n):
if (current_sum - arr[j]) in seen:
count += 1
seen.add(arr[j])
return count
# Example usage
arr = [1, 4, 6, 7, 10]
target_sum = 17
print(count_triplets(arr, target_sum))- Kadane’s Algorithm:
Problem: Find the maximum sum of any contiguous subarray.
Example: For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum sum is 6 for the subarray [4, -1, 2, 1].
Approach: Traverse the array while keeping track of the maximum sum ending at the current position and updating the global maximum.
def kadane_algorithm(arr):
max_current = max_global = arr[0]
for i in range(1, len(arr)):
max_current = max(arr[i], max_current + arr[i])
if max_current > max_global:
max_global = max_current
return max_global
# Example usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane_algorithm(arr))- Missing Number in Array:
Problem: Find the missing number in an array containing numbers from 1 to n with one number missing.
Example: For the array [1, 2, 4, 5] with n = 5, the missing number is 3.
Approach: Calculate the expected sum of numbers from 1 to n and subtract the sum of the array to find the missing number.
def find_missing_number(arr, n):
total_sum = n * (n + 1) // 2
array_sum = sum(arr)
return total_sum - array_sum
# Example usage
arr = [1, 2, 4, 5]
n = 5
print(find_missing_number(arr, n))- Merge Two Sorted Arrays:
Problem: Merge two sorted arrays into a single sorted array.
Example: For the arrays [1, 3, 5] and [2, 4, 6], the merged array is [1, 2, 3, 4, 5, 6].
Approach: Use two pointers, one for each array, and compare elements to merge them in sorted order.
def merge_sorted_arrays(arr1, arr2):
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
merged.append(arr1[i])
i += 1
else:
merged.append(arr2[j])
j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
# Example usage
arr1 = [1, 3, 5]
arr2 = [2, 4, 6]
print(merge_sorted_arrays(arr1, arr2))- Rearrange Array Alternatively:
Problem: Rearrange an array such that elements are alternatively less than and greater than their neighbors.
Example: For the array [1, 3, 2, 7, 6, 5], rearrange it to [1, 7, 2, 6, 3, 5].
Approach: Sort the array and then use two pointers or swapping to rearrange elements.
def rearrange_array_alternatively(arr):
n = len(arr)
arr.sort()
result = [0] * n
left, right = 0, n - 1
for i in range(n):
if i % 2 == 0:
result[i] = arr[right]
right -= 1
else:
result[i] = arr[left]
left += 1
return result
# Example usage
arr = [1, 2, 3, 4, 5, 6]
print(rearrange_array_alternatively(arr))- Number of Pairs:
Problem: Count pairs of elements in an array that satisfy a given condition, such as summing to a specific value.
Example: For the array [1, 2, 3, 4, 3] and sum 6, the pairs are (2, 4) and (3, 3).
Approach: Use a hash map to keep track of elements and count pairs efficiently.
def count_pairs(arr, target_sum):
count = 0
seen = set()
for num in arr:
if target_sum - num in seen:
count += 1
seen.add(num)
return count
# Example usage
arr = [1, 2, 3, 4, 3]
target_sum = 6
print(count_pairs(arr, target_sum))- Inversion of Array:
Problem: Count the number of inversions in an array, where an inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j].
Example: For the array [2, 3, 8, 6, 1], the number of inversions is 5.
Approach: Use a modified merge sort to count inversions during the merging process.
def merge_and_count(arr, temp_arr, left, mid, right):
i = left
j = mid + 1
k = left
inv_count = 0
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)
j += 1
k += 1
while i <= mid:
temp_arr[k] = arr[i]
i += 1
k += 1
while j <= right:
temp_arr[k] = arr[j]
j += 1
k += 1
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 = [2, 3, 8, 6, 1]
print(count_inversions(arr))- Sort an Array of 0s, 1s, and 2s:
Problem: Sort an array containing only 0s, 1s, and 2s efficiently.
Example: For the array [2, 0, 1, 2, 1, 0], the sorted array is [0, 0, 1, 1, 2, 2].
Approach: Use the Dutch National Flag algorithm with three pointers to sort in a single pass.
def sort_012(arr):
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[high], arr[mid] = arr[mid], arr[high]
high -= 1
return arr
# Example usage
arr = [2, 0, 1, 2, 1, 0]
print(sort_012(arr))- Equilibrium Point:
Problem: Find the index in an array where the sum of elements on the left is equal to the sum of elements on the right.
Example: For the array [1, 3, 5, 2, 2], the equilibrium index is 2.
Approach: Calculate the total sum of the array and then use a running sum to find the equilibrium index.
def find_equilibrium_point(arr):
total_sum = sum(arr)
left_sum = 0
for i in range(len(arr)):
total_sum -= arr[i]
if left_sum == total_sum:
return i
left_sum += arr[i]
return -1
# Example usage
arr = [1, 3, 5, 2, 2]
print(find_equilibrium_point(arr))
11. Leaders in an Array:
Problem: Find all elements in an array that are greater than all elements to their right.
Example: For the array [16, 17, 4, 3, 5, 2], the leaders are 17 and 5.
Approach: Traverse the array from right to left, keeping track of the maximum value seen so far.
def find_leaders(arr):
leaders = []
max_from_right = arr[-1]
leaders.append(max_from_right)
for i in range(len(arr) - 2, -1, -1):
if arr[i] > max_from_right:
max_from_right = arr[i]
leaders.append(max_from_right)
return leaders[::-1]
# Example usage
arr = [16, 17, 4, 3, 5, 2]
print(find_leaders(arr))
12. Minimum Platforms:
Problem: Find the minimum number of platforms required for a train station so that no train has to wait.
Example: For arrival times [10:00, 10:15, 10:30] and departure times [10:30, 10:45, 11:00], the minimum platforms needed is 2.
Approach: Use a sorted list of arrival and departure times and a sweep line algorithm to find the peak overlap.
def find_minimum_platforms(arrivals, departures):
arrivals.sort()
departures.sort()
platforms_needed = 1
max_platforms = 1
i = 1
j = 0
while i < len(arrivals) and j < len(departures):
if arrivals[i] <= departures[j]:
platforms_needed += 1
i += 1
else:
platforms_needed -= 1
j += 1
max_platforms = max(max_platforms, platforms_needed)
return max_platforms
# Example usage
arrivals = [10, 15, 30]
departures = [15, 30, 45]
print(find_minimum_platforms(arrivals, departures))
13. Reverse Array in Groups:
Problem: Reverse the elements of an array in groups of a given size.
Example: For the array [1, 2, 3, 4, 5, 6] and group size 2, the result is [2, 1, 4, 3, 6, 5].
Approach: Use a loop to reverse elements in chunks of the specified size.
def reverse_in_groups(arr, k):
n = len(arr)
for i in range(0, n, k):
left = i
right = min(i + k - 1, n - 1)
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
# Example usage
arr = [1, 2, 3, 4, 5, 6]
k = 2
print(reverse_in_groups(arr, k))
14. K’th Smallest Element:
Problem: Find the k-th smallest element in an array.
Example: For the array [7, 10, 4, 3, 20, 15] and k = 4, the 4th smallest element is 10.
Approach: Use a min-heap or quickselect algorithm to find the k-th smallest element efficiently.
import heapq
def kth_smallest(arr, k):
return heapq.nsmallest(k, arr)[-1]
# Example usage
arr = [7, 10, 4, 3, 20, 15]
k = 4
print(kth_smallest(arr, k))
15. Trapping Rain Water:
Problem: Calculate the amount of water trapped between bars of varying heights after rainfall.
Example: For the heights [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the water trapped is 6.
Approach: Use two pointers or dynamic programming to calculate trapped water based on the heights of bars.
def trap_rain_water(heights):
n = len(heights)
if n == 0:
return 0
left_max = [0] * n
right_max = [0] * n
left_max[0] = heights[0]
right_max[n - 1] = heights[n - 1]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], heights[i])
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], heights[i])
water_trapped = 0
for i in range(n):
water_trapped += min(left_max[i], right_max[i]) - heights[i]
return water_trapped
# Example usage
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rain_water(heights))
16. Pythagorean Triplet:
Problem: Find if there exists a triplet in an array that satisfies the Pythagorean theorem, i.e., a^2 + b^2 = c^2.
Example: For the array [3, 1, 4, 6, 5], the triplet (3, 4, 5) satisfies the theorem.
Approach: Sort the array, then use two pointers to check for triplets that satisfy the equation.
def is_pythagorean_triplet(arr):
arr = [x * x for x in arr]
arr.sort()
n = len(arr)
for i in range(n - 1, 1, -1):
left = 0
right = i - 1
while left < right:
if arr[left] + arr[right] == arr[i]:
return True
elif arr[left] + arr[right] < arr[i]:
left += 1
else:
right -= 1
return False
# Example usage
arr = [3, 1, 4, 6, 5]
print(is_pythagorean_triplet(arr))
17. Chocolate Distribution Problem:
Problem: Find if there exists a triplet in an array that satisfies the Pythagorean theorem, i.e., a^2 + b^2 = c^2.
Example: For the array [3, 1, 4, 6, 5], the triplet (3, 4, 5) satisfies the theorem.
Approach: Sort the array, then use two pointers to check for triplets that satisfy the equation.
def chocolate_distribution_problem(arr, m):
if m > len(arr):
return -1
arr.sort()
min_diff = float('inf')
for i in range(len(arr) - m + 1):
min_diff = min(min_diff, arr[i + m - 1] - arr[i])
return min_diff
# Example usage
arr = [12, 4, 7, 9, 5, 6, 8, 11]
m = 5
print(chocolate_distribution_problem(arr, m))
18. Stock Buy and Sell:
Problem: Find the maximum profit from buying and selling stocks given their prices on different days.
Example: For the prices [7, 1, 5, 3, 6, 4], the maximum profit is 5 (buy at 1 and sell at 6).
Approach: Traverse the prices while keeping track of the minimum price and maximum profit.
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit
# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))
19. Element with Left Side Smaller and Right Side Greater:
def element_with_left_smaller_right_greater(arr):
n = len(arr)
left_min = [None] * n
right_max = [None] * n
left_min[0] = float('-inf')
for i in range(1, n):
left_min[i] = max(left_min[i - 1], arr[i - 1])
right_max[n - 1] = float('inf')
for i in range(n - 2, -1, -1):
right_max[i] = min(right_max[i + 1], arr[i + 1])
for i in range(n):
if left_min[i] < arr[i] < right_max[i]:
return arr[i]
return -1
# Example usage
arr = [1, 3, 5, 2, 8]
print(element_with_left_smaller_right_greater(arr))
20. Convert Array into Zig-Zag Fashion:
def zigzag_conversion(arr):
flag = True
for i in range(len(arr) - 1):
if flag:
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
else:
if arr[i] < arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
flag = not flag
return arr
# Example usage
arr = [4, 3, 7, 8, 6, 2, 1]
print(zigzag_conversion(arr))
21. Last Index of 1:
def last_index_of_1(arr):
for i in range(len(arr) - 1, -1, -1):
if arr[i] == 1:
return i
return -1
# Example usage
arr = [0, 1, 0, 1, 0, 1]
print(last_index_of_1(arr))
22. Spirally Traversing a Matrix:
def spiral_traversal(matrix):
result = []
if not matrix:
return result
top, bottom, left, right = 0, len(matrix), 0, len(matrix[0])
while top < bottom and left < right:
for i in range(left, right):
result.append(matrix[top][i])
top += 1
for i in range(top, bottom):
result.append(matrix[i][right - 1])
right -= 1
if not (top < bottom and left < right):
break
for i in range(right - 1, left - 1, -1):
result.append(matrix[bottom - 1][i])
bottom -= 1
for i in range(bottom - 1, top - 1, -1):
result.append(matrix[i][left])
left += 1
return result
# Example usage
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(spiral_traversal(matrix))
22. Largest Number Formed from an Array:
from functools import cmp_to_key
def compare(x, y):
if x + y > y + x:
return -1
else:
return 1
def largest_number(arr):
arr = [str(x) for x in arr]
arr.sort(key=cmp_to_key(compare))
return str(int(''.join(arr)))
# Example usage
arr = [54, 546, 548, 60]
print(largest_number(arr))
