Practice Data Structures And Algorithms
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
- Example 1:
Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which
is a contiguous subarray.
- Solution:
class Solution:
# find the sum of contiguous subarray with maximum sum.
def maxSubArraySum(self,arr,N):
maxarr = arr[0]
su = arr[0]
for i in range(1,N):
su = max(arr[i], su + arr[i])
maxarr = max(maxarr,su)
return maxarr
Given an array of N integers arr[] where each element represents the max number of steps that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.
- Example 1:
Input:
N = 11
arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3
Explanation:
First jump from 1st element to 2nd
element with value 3. Now, from here
we jump to 5th element with value 9,
and from here we will jump to the last.
- Solution:
class Solution:
def minJumps(self, arr, n):
maxend = 0
currend= 0
jump = 0
if n == 1:
return 0
for i in range(n):
maxend = max(maxend, i+arr[i])
if maxend >= n-1:
return jump+1
elif i == maxend:
return -1
elif i==currend:
jump+=1
currend=maxend
return jump
Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.
- Example 1:
Input:
N = 5
A[] = {1,2,3,5}
Output: 4
- Solution:
class Solution:
def MissingNumber(self,array,n):
# return first element of differences of sets
return list(set([i for i in range(1, n+1)]) - set(array))[0]
Given a string 's'. The task is to find the smallest window length that contains all the characters of the given string at least one time. For eg. A = aabcbcdbca, then the result would be 4 as of the smallest window will be dbca.
- Example 1:
Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"
- Example 2:
Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"
- Solution:
import numpy as np
class Solution:
def findSubString(self, str):
v1,v2={},{}
for a in str:
if a not in v1:
v1[a]=0
v1[a]+=1
i,j,res,n=0,0,1e5+1,len(str)
while j<n:
if str[j] not in v2:
v2[str[j]]=0
v2[str[j]]+=1
if (len(v2)==len(v1)): # means all characters has been counted at least once
while len(v2)==len(v1):
v2[str[i]]-=1
if v2[str[i]]==0:
del v2[str[i]]
i+=1
res=min(res,2+j-i)
j+=1
return res
Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.
- Example 1:
Input:
N = 6
arr[] = {3,0,0,2,0,4}
Output:
10
- Solution:
class Solution:
def trappingWater(self, arr,n):
totalResult = 0
# find all combinations of leftHeightLimitation --- rightHeightLimitation
# not only from indexes 0 to n - 1
leftIndex = 0
rightIndex = leftIndex + 1
while rightIndex < n:
leftHeightLimitation = arr[leftIndex]
if leftHeightLimitation == max(arr[leftIndex: n]):
# if left is max, look for next right max
if leftIndex == n - 2:
# when reaching end of array
rightIndex = n - 1
else:
rightIndex = leftIndex + 1 + arr[leftIndex + 1: n].index(max(arr[leftIndex + 1: n]))
rightHeightLimitation = arr[rightIndex]
else:
# if left is not max, look for next upper right
rightHeightLimitation = arr[rightIndex]
while leftHeightLimitation > rightHeightLimitation and rightIndex < n - 1:
rightIndex = rightIndex + 1
rightHeightLimitation = arr[rightIndex]
localArr = arr[leftIndex:rightIndex + 1]
localMinHeightLimitation = min(leftHeightLimitation, rightHeightLimitation)
difference = list(map(lambda h: localMinHeightLimitation - h if h < localMinHeightLimitation else 0, localArr))
result = sum(difference[1:-1])
totalResult = totalResult + result
leftIndex = rightIndex
rightIndex = leftIndex + 1
return totalResult
Desc
- Example 1:
example
- Solution:
code