Pascal's Triangle
def generate_pascals_triangle(n):
triangle = []
for i in range(n):
row = [1]*(i+1)
for j in range(1, i):
row[j] = triangle[i-1][j-1] + triangle[i-1][j]
[Link](row)
return triangle
# Example usage:
n=5
triangle = generate_pascals_triangle(n)
for row in triangle:
print(row)
Output:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
Majority Element (Appears More Than n/3 Times)
def majority_element(nums):
if not nums:
return []
count1 = count2 = 0
candidate1 = candidate2 = None
for num in nums:
if candidate1 == num:
count1 += 1
elif candidate2 == num:
count2 += 1
elif count1 == 0:
candidate1, count1 = num, 1
elif count2 == 0:
candidate2, count2 = num, 1
else:
count1 -= 1
count2 -= 1
result = []
for candidate in [candidate1, candidate2]:
if [Link](candidate) > len(nums) // 3:
[Link](candidate)
return result
# Example usage:
nums = [1, 2, 2, 3, 2]
print(majority_element(nums))
Output:
[2]
3-Sum Problem
def three_sum(nums):
[Link]()
res = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
[Link]([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
# Example usage:
nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))
Output:
[[-1, -1, 2], [-1, 0, 1]]
4-Sum Problem
def four_sum(nums, target):
[Link]()
res = []
n = len(nums)
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
l, r = j+1, n-1
while l < r:
s = nums[i] + nums[j] + nums[l] + nums[r]
if s < target:
l += 1
elif s > target:
r -= 1
else:
[Link]([nums[i], nums[j], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
# Example usage:
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(four_sum(nums, target))
Output:
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Largest Subarray with 0 Sum
def max_len_zero_sum_subarray(arr):
sum_dict = {}
max_len = 0
curr_sum = 0
for i in range(len(arr)):
curr_sum += arr[i]
if curr_sum == 0:
max_len = i + 1
elif curr_sum in sum_dict:
max_len = max(max_len, i - sum_dict[curr_sum])
else:
sum_dict[curr_sum] = i
return max_len
# Example usage:
arr = [15, -2, 2, -8, 1, 7, 10, 23]
print(max_len_zero_sum_subarray(arr))
Output:
Count Number of Subarrays with Given XOR K
def count_subarrays_with_xor(arr, K):
from collections import defaultdict
count = 0
xor = 0
freq = defaultdict(int)
for num in arr:
xor ^= num
if xor == K:
count += 1
if xor ^ K in freq:
count += freq[xor ^ K]
freq[xor] += 1
return count
# Example usage:
arr = [4, 2, 2, 6, 4]
K=6
print(count_subarrays_with_xor(arr, K))
Output:
Merge Overlapping Sub-Interval
def merge_intervals(intervals):
if not intervals:
return []
[Link](key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
prev = merged[-1]
if current[0] <= prev[1]:
prev[1] = max(prev[1], current[1])
else:
[Link](current)
return merged
# Example usage:
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge_intervals(intervals))
Output:
[[1, 6], [8, 10], [15, 18]]
Merge Two Sorted Arrays Without Extra Space
def merge(arr1, arr2):
n, m = len(arr1), len(arr2)
for i in range(n):
if arr1[i] > arr2[0]:
arr1[i], arr2[0] = arr2[0], arr1[i]
first = arr2[0]
k=1
while k < m and arr2[k] < first:
arr2[k-1] = arr2[k]
k += 1
arr2[k-1] = first
# Example usage:
arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
merge(arr1, arr2)
print("First Array:", arr1)
print("Second Array:", arr2)
Output:
First Array: [1, 2, 3, 5, 8, 9]
Second Array: [10, 13, 15, 20]
Repeating & Missing Number
def find_two_elements(arr):
n = len(arr)
repeating = missing = -1
for x in arr:
if arr[abs(x) - 1] < 0:
repeating = abs(x)
else:
arr[abs(x) - 1] *= -1
for i in range(n):
if arr[i] > 0:
missing = i + 1
break
return repeating, missing
# Example
arr = [3, 1, 3]
print(find_two_elements(arr)) # Output: (3, 2)
Count Inversions
def count_inversions(arr):
def merge_count(a, temp, left, mid, right):
i, j, k = left, mid, left
inv = 0
while i < mid and j < right:
if a[i] <= a[j]:
temp[k] = a[i]; i += 1
else:
temp[k] = a[j]
inv += mid - i
j += 1
k += 1
while i < mid:
temp[k] = a[i]; i += 1; k += 1
while j < right:
temp[k] = a[j]; j += 1; k += 1
a[left:right] = temp[left:right]
return inv
def sort_count(a, temp, l, r):
if r - l <= 1: return 0
m = (l + r) // 2
inv = sort_count(a, temp, l, m)
inv += sort_count(a, temp, m, r)
inv += merge_count(a, temp, l, m, r)
return inv
return sort_count(arr[:], [0]*len(arr), 0, len(arr))
# Example
arr = [4, 3, 2, 1]
print(count_inversions(arr))
Output:
Reverse Pairs
def reverse_pairs(nums):
def sort(lo, hi):
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
inv = sort(lo, mid) + sort(mid, hi)
j = mid
for i in range(lo, mid):
while j < hi and nums[i] > 2 * nums[j]:
j += 1
inv += j - mid
nums[lo:hi] = sorted(nums[lo:hi])
return inv
return sort(0, len(nums))
# Example
nums = [1, 3, 2, 3, 1]
print(reverse_pairs(nums))
Output:
Maximum Product Subarray
def max_product_subarray(nums):
cur_max = cur_min = result = nums[0]
for num in nums[1:]:
if num < 0:
cur_max, cur_min = cur_min, cur_max
cur_max = max(num, cur_max * num)
cur_min = min(num, cur_min * num)
result = max(result, cur_max)
return result
# Example
nums = [-2, 6, -3, -10, 0, 2]
print(max_product_subarray(nums))
Output:
180