Arrays
1. Subarray with given sum
2. Count the triplets
3. Kadane’s Algorithm
4. Missing number in array
5. Merge two sorted arrays
6. Rearrange array alternatively
7. Number of pairs
8. Inversion of Array
9. Sort an array of 0s, 1s and 2s
10. Equilibrium point
11. Leaders in an array
12. Minimum Platforms
13. Reverse array in groups
14. K’th smallest element
15. Trapping Rain Water
16. Pythagorean Triplet
17. Chocolate Distribution Problem
18. Stock buy and sell
19. Element with left side smaller and right side greater
20. Convert array into Zig-Zag fashion
21. Last Index of 1
22. Spirally traversing a matrix
23. Largest Number formed from an Array
Q1 . Subarray with given sum
class Solution:
def subArraySum(self,arr, n, s):
curr_sum = arr[0]
start = 0
i = 1
while i <= n:
while curr_sum > s and start < i - 1:
curr_sum -= arr[start]
start += 1
if curr_sum == s:
return [start + 1, i]
if i < n:
curr_sum += arr[i]
i += 1
return [-1]
Q2 count the triplets (TLE)
class Solution:
def countTriplet(self, arr, n):
count = 0
for i in range(n):
for j in range(i + 1, n):
sum = arr[i] + arr[j]
if sum in arr:
count += 1
return count
Q3 Kadane’s Algorithm
class Solution:
def maxSubArraySum(self,arr,N):
curr_sum = 0
max_sum = arr[0]
for i in range(N):
curr_sum += arr[i]
max_sum = max(max_sum, curr_sum)
if curr_sum < 0: curr_sum = 0
return max_sum
Q4 Missing number in array
class Solution:
def MissingNumber(self,array,n):
Total_sum = n * (n + 1)//2
actual_sum = 0
for i in range(n - 1):
actual_sum += array[i]
return Total_sum - actual_sum
Q5 Merge without extra space (naive method)
class Solution:
def merge(self,arr1,arr2,n,m):
arr = arr1 + arr2
arr.sort()
for i in range(n + m):
if i < n:
arr1[i] = arr[i]
if i >= n:
arr2[i - n] = arr[i]
Optimized method (n * logn)
from math import ceil
class Solution:
def merge(self,arr1,arr2,n,m):
gap = n + m
gap = ceil(gap/2)
while gap > 0:
i = 0
while i + gap < n:
if arr1[i] > arr1[i + gap]:
arr1[i], arr1[i + gap] = \
arr1[i + gap], arr1[i]
i += 1
if gap > n:
j = gap - n
else:
j = 0
while i < n and j < m:
if arr1[i] > arr2[j]:
arr1[i], arr2[j] = \
arr2[j], arr1[i]
i += 1
j += 1
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]
j += 1
if gap <= 1:
gap = 0
else:
gap = ceil(gap/2)
Q6 Rearrange the array Alternately (naive method)
class Solution:
def rearrange(self,arr, n):
arr1 = arr[:]
k = 0
for i in range(0, n, 2):
arr[i] = arr1[n - 1 - k]
k += 1
k = 0
for i in range(1, n, 2):
arr[i] = arr1[k]
k += 1
Optimized method (formula used)
class Solution:
def rearrange(self,arr, n):
me = arr[n - 1] + 1
i = 0
j = n -1
k = 0
for i in range(n):
if i % 2 == 0:
arr[i] = arr[i] + (arr[j] % me) * me
j -= 1
else:
arr[i] = arr[i] + (arr[k] % me) * me
k += 1
for i in range(n):
arr[i] = arr[i]//me
Q7 Number of pairs
from bisect import bisect_right
class Solution:
def countPairs(self,a,b,M,N):
b.sort()
count_of_0 = bisect_right(b, 0)
count_of_1 = bisect_right(b, 1) - count_of_0
count_of_2 = bisect_right(b, 2) - bisect_right(b,1)
count = 0
for x in a:
if x == 0: continue
elif x == 1:
count += count_of_0
elif x == 2:
count += N - bisect_right(b, 4) + \
count_of_0 + count_of_1
elif x == 3:
count += N - bisect_right(b, 3) + \
count_of_2 + count_of_0 + count_of_1
else:
count += N - bisect_right(b, x) + \
count_of_0 + count_of_1
return count
