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]

triangle.append(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)

if not nums:

return []

count1 = count2 = 0

candidate1 = candidate2 = None

for num in nums:

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 nums.count(candidate) > len(nums) // 3:

result.append(candidate)

return result

# Example usage:

nums = [1, 2, 2, 3, 2]

print(majority_element(nums))

Output:

[2]

3-Sum Problem
def three_sum(nums):

nums.sort()

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:

res.append([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):

nums.sort()

res = []

n = len(nums)

for i in range(n-3):

if i > 0 and nums[i] == nums[i-1]:

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:

res.append([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

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

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

if not intervals:

return []

intervals.sort(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:

merged.append(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]]

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

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

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