Lists-Array2 Flashcards
How to find every increasing sequence?
Traverese the array:
if A[i-1] > A[i] —> begining of the increasing sequence—> svae the index , beg =i+1
if A[i-1] < A[i] and (i+1 == len(A) or A[i] > A[i+1])– :end = i+1
Find maximum profit earned by buying and selling shares any number of times
Given a list containing future prediction of share prices, find the maximum profit earned by buying and selling shares any number of times with the constraint, a new transaction can only start after the previous transaction is complete, i.e., we can only hold at most one share at a time.
Stock Prices: {1, 5, 2, 3, 7, 6, 4, 5}
Total profit earned is 10
Buy on day 1 and sell on day 2
Buy on day 3 and sell on day 5
Buy on day 7 and sell on day 8
Stock Prices: {10, 8, 6, 5, 4, 2}
Total profit earned is 0
problem allows us to make unlimited stock transactions. The idea is to traverse the given list of prices and find a local minimum of every increasing sequence. For example, the increasing sequences of length 2 or more in the array {1, 5, 2, 3, 7, 6, 4, 5} are {1, 5}, {2, 3, 7}, and {4, 5}. The local minimum of each sequence is 1, 2 and 4, respectively. We can gain maximum profit if we buy the shares at the starting of every increasing sequence (local minimum) and sell them at the end of the increasing sequence (local maximum).
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the total number of given days.
################## code # Function to find the maximum profit earned by buying and # selling shares any number of times def findMaxProfit(price):
# keep track of the maximum profit gained
profit = 0
# initialize the local minimum to the first element's index
j = 0
# start from the second element
for i in range(1, len(price)):
# update the local minimum if a decreasing sequence is found
if price[i - 1] > price[i]:
j = i
# sell shares if the current element is the peak, i.e.,
# (`previous <= current > next`)
if price[i - 1] <= price[i] and \
(i + 1 == len(price) or price[i] > price[i + 1]):
profit += (price[i] - price[j])
print(f"Buy on day {j + 1} and sell on day {i + 1}")
return profit
Find maximum profit earned by buying and selling shares one time, such that you sell first and sell after
This problem is similar to “finding the max difference between two elements of the array such that max occurs after min element”.
We start from the right side of the array. Set the max number as the last element. then we traverse the array and look for two conditions:
1) find another max number in index i
2) update the max diff
The idea is to traverse the array from the right and keep track of the maximum difference found so far. If the current element is less than the maximum element found so far and their difference is more than the maximum difference found so far, update the maximum difference with the current difference.
complexity O(n)
code###########
import sys
# Function to calculate the maximum difference between two elements in a # list such that a smaller element appears before a larger element def getMaxDiff(A):
diff = -sys.maxsize
n = len(A)
if n == 0:
return diff
max_so_far = A[n - 1]
# traverse the list from the right and keep track of the maximum element
for i in reversed(range(n - 1)):
# update `max_so_far` if the current element is greater than the
# maximum element
if A[i] >= max_so_far:
max_so_far = A[i]
# if the current element is less than the maximum element,
# then update the difference if required
else:
diff = max(diff, max_so_far - A[i])
# return difference
return diff
Trapping Rain Water Problem
Trapping rainwater problem: Find the maximum amount of water that can be trapped within a given set of bars where each bar’s width is 1 unit.
https://www.techiedelight.com/trapping-rain-water-within-given-set-bars/
1- Direction First:
we know that water can be trapped between two maximum heights. So we start from the right side of the given heights array.
set the max_height to the last element. then we traverse the height array in reverse order and check to condition.
1) update max height if: height[i] >= max_height
2) calculate the water_trapped = max_height - height[i]
2 - second direction:
we have two indexes left starting from the first elem and right starting
from last elem of the height list.
Then while left < right, we check wether height[left] < hight[right], so we
1) move left index 2) update max_left = max(max_left, height[left])
3) water += (max_heigh- heights[left])
the something for right
code direction 1:
def rain_tarp(Arr):
n = len(Arr) max_bar = Arr[n-1] area = 0
for i in reversed(range(n)):
# update max_bar
if Arr[i] >= max_bar:
max_bar = Arr[i]
else:
area += max_bar - Arr[i] print lst return area
code: Second Approach
# Function to find the amount of water that can be trapped within # a given set of bars in linear time and constant space def trap(heights):
# maintain two pointers left and right, pointing to the leftmost and
# rightmost index of the input list
(left, right) = (0, len(heights) - 1)
water = 0
maxLeft = heights[left]
maxRight = heights[right]
while left < right:
if heights[left] <= heights[right]:
left = left + 1
maxLeft = max(maxLeft, heights[left])
water += (maxLeft - heights[left])
else:
right = right - 1
maxRight = max(maxRight, heights[right])
water += (maxRight - heights[right])
return water
if __name__ == ‘__main__’:
heights = [7, 0, 4, 2, 5, 0, 6, 4, 0, 5]
print("The maximum amount of water that can be trapped is", trap(heights))
Maximum Product Subarray Problem
Given an integer array, find the subarray that has the maximum product of its elements. The solution should return the maximum product of elements among all possible subarrays.
The problem differs from the problem of finding the maximum product subsequence. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.
A naive solution would be to consider every subarray and find the product of their elements. Finally, return the maximum product found among all subarrays. The implementation can be seen here. The time complexity of this solution is O(n2), where n is the size of the input.
A better solution will be to maintain two variables to store the maximum and minimum product ending in the current position. Then traverse the array once, and for every index i in the array, update the maximum and minimum product ending at A[i]. Update the result if the maximum product ending at any index is more than the maximum product found so far.
O(n)
code##########
# Function to return the maximum product of a sublist of a given list def findMaxProduct(A):
# base case
if not len(A):
return 0
# maintain two variables to store the maximum and minimum product
# ending at the current index
max_ending = min_ending = A[0]
# to store the maximum product sublist found so far
max_so_far = A[0]
# traverse the given list
for i in range(1, len(A)):
temp = max_ending
# update the maximum product ending at the current index
max_ending = max(A[i], max(A[i] * max_ending, A[i] * min_ending))
# update the minimum product ending at the current index
min_ending = min(A[i], min(A[i] * temp, A[i] * min_ending))
max_so_far = max(max_so_far, max_ending)
# return maximum product
return max_so_far
if __name__ == ‘__main__’:
A = [-6, 4, -5, 8, -10, 0, 8]
print("The maximum product of a sublist is", findMaxProduct(A))
0–1 Knapsack Problem
In the 0–1 Knapsack problem, we are given a set of items, each with a weight and a value, and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Input:
value = [ 20, 5, 10, 40, 15, 25 ]
weight = [ 1, 2, 3, 8, 7, 4 ]
int W = 10
Output: Knapsack value is 60
value = 20 + 40 = 60 weight = 1 + 8 = 9 < W
The idea is to use recursion to solve this problem. For each item, there are two possibilities:
Include the current item in the knapsack and recur for remaining items with knapsack’s decreased capacity. If the capacity becomes negative, do not recur or return -INFINITY.
Exclude the current item from the knapsack and recur for the remaining items.
Finally, return the maximum value we get by including or excluding the current item. The base case of the recursion would be when no items are left, or capacity becomes 0.
The time complexity of the above solution is exponential and occupies space in the call stack.
code##################
mport sys
# Values (stored in list `v`) # Weights (stored in list `w`) # Total number of distinct items `n` # Knapsack capacity `W` def knapsack(v, w, n, W):
# base case: Negative capacity
if W < 0:
return -sys.maxsize
# base case: no items left or capacity becomes 0
if n < 0 or W == 0:
return 0
# Case 1. Include current item `n` in knapsack `v[n]` and recur for
# remaining items `n-1` with decreased capacity `W-w[n]`
include = v[n] + knapsack(v, w, n - 1, W - w[n])
# Case 2. Exclude current item `v[n]` from the knapsack and recur for
# remaining items `n-1`
exclude = knapsack(v, w, n - 1, W)
# return maximum value we get by including or excluding the current item
return max(include, exclude)
# 0–1 Knapsack problem if \_\_name\_\_ == '\_\_main\_\_':
# input: a set of items, each with a weight and a value v = [20, 5, 10, 40, 15, 25] w = [1, 2, 3, 8, 7, 4]
# knapsack capacity
W = 10
print('Knapsack value is', knapsack(v, w, len(v) - 1, W))
############### We can also solve this problem in a bottom-up manner. In the bottom-up approach, we solve smaller subproblems first, then solve larger subproblems from them. The following bottom-up approach computes T[i][j], for each 1 <= i <= n and 0 <= j <= W, which is the maximum value that can be attained with weight less than or equal to j and using items up to first i items. It uses the value of smaller values i and j already computed. It has the same asymptotic runtime as Memoization but no recursion overhead.
The time complexity of the above bottom-up solution is O(n.W) and requires O(n.W) extra space, where n is the total number of items in the input and W is the knapsack’s capacity.
code##########
# Input: # Values (stored in list `v`) # Weights (stored in list `w`) # Total number of distinct items `n` # Knapsack capacity `W` def knapsack(v, w, W):
# `T[i][j]` stores the maximum value of knapsack having weight less
# than equal to `j` with only first `i` items considered.
T = [[0 for x in range(W + 1)] for y in range(len(v) + 1)]
# do for i'th item
for i in range(1, len(v) + 1):
# consider all weights from 0 to maximum capacity `W`
for j in range(W + 1):
# don't include the i'th element if `j-w[i-1]` is negative
if w[i - 1] > j:
T[i][j] = T[i - 1][j]
else:
# find the maximum value we get by excluding or including the i'th item
T[i][j] = max(T[i - 1][j], T[i - 1][j - w[i - 1]] + v[i - 1])
# return maximum value
return T[len(v)][W]
if __name__ == ‘__main__’:
# input: a set of items, each with a weight and a value v = [20, 5, 10, 40, 15, 25] w = [1, 2, 3, 8, 7, 4]
# knapsack capacity
W = 10
Difference between Subarray, Subsequence, and Subset
Discuss the difference between a subarray, a substring, a subsequence, and a subset.
- Subarray
A subarray is a slice from a contiguous array (i.e., occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
Please note that there are precisely n×(n+1)/2 subarrays in an array of size n. Also, there is no such thing as a contiguous subarray. The prefix contiguous is sometimes applied to make the context more clear. So, a contiguous subarray is just another name for a subarray.
######### code#####################
# Function to print all sublists of the specified list
def printallSublists(nums):
# consider all sublists starting from i
for i in range(len(nums)):
# consider all sublists ending at `j`
for j in range(i, len(nums)):
# Function to print a sublist formed by [i, j]
print(nums[i: j + 1])
__________________________
2. Substring
A substring of a string s is a string s’ that occurs in s. A substring is almost similar to a subarray, but it is in the context of strings.
For example, the substrings of string ‘apple’ are ‘apple’, ‘appl’, ‘pple’, ‘app’, ‘ppl’, ‘ple’, ‘ap’, ‘pp’, ‘pl’, ‘le’, ‘a’, ‘p’, ‘l’, ‘e’, ‘’.
############### code########
# Function to print all non-empty substrings of the specified string
def printAllSubstrings(s):
# consider all substrings starting from i
for i in range(len(s)):
# consider all substrings ending at j
for j in range(i, len(s)):
print(s[i: j + 1], end=' ')
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. Subsequence
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, {nums, B, D} is a subsequence of sequence {nums, B, C, D, E} obtained after removing {C} and {E}.
People are often confused between a subarray/substring and a subsequence. A subarray or substring will always be contiguous, but a subsequence need not be contiguous. That is, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequence and subarray are the same.
In other words, the subsequence is a generalization of a substring, or substring is a refinement of the subsequence. For example, {nums, C, E} is a subsequence of {nums, B, C, D, E}, but not a substring, and {nums, B, C} is both a subarray and a subsequence.
Please note that a subsequence can be in the context of both arrays and strings. Generating all subsequences of an array/string is equivalent to generating a power set of an array/string. For a given set, S, we can find the power set by generating all binary numbers between 0 and 2n-1, where n is the size of the given set.
############## code########
# Function to print all subsequences of the specified string
def findPowerSet(seq):
# N stores the total number of subsets
N = int(pow(2, len(seq)))
# generate each subset one by one
result = []
for i in range(N):
s = ''
# check every bit of `i`
for j in range(len(seq)):
# if j'th bit of `i` is set, print S[j]
if (i & (1 << j)) != 0:
s += seq[j]
result.append(s)
print(result)
———————-____________________________
4. Subset
A subset is any possible combination of the original set. The term subset is often used for subsequence, but that’s not right. A subsequence always maintains the relative order of the array elements (i.e., increasing index), but there is no such restriction on a subset. For example, {3, 1} is a valid subset of {1, 2, 3, 4, 5}, but it is neither a subsequence nor a subarray.
It is worth noting that all subarrays are subsequences and all subsequences are a subset, but the reverse is not valid. For instance, a subarray {1, 2} of array {1, 2, 3, 4, 5} is also a subsequence and a subset.
Find the frequency of each element in a sorted array containing duplicates
Given a sorted array containing duplicates, efficiently find each element’s frequency without traversing the whole array.
Input: [2, 2, 2, 4, 4, 4, 5, 5, 6, 8, 8, 9]
Output: {2: 3, 4: 3, 5: 2, 6: 1, 8: 2, 9: 1}
A simple solution would be to run a linear search on the array and count the number of occurrences of each element and finally print them. The problem with this approach is that its worst-case time complexity is O(n), where n is the input size, and we are scanning the whole array (violating problem constraints).
We can easily solve this problem in O(m.log(n)) time by taking advantage of the fact that the input is sorted and contains duplicates. Here m is the total number of distinct elements in the array, and n is the input size.
Iteratieve approach :
# Function to find the frequency of each element in a sorted list def findFrequency(nums):
# dictionary to store the frequency of each element in the list
freq = {}
# search space is nums[left…right]
(left, right) = (0, len(nums) - 1)
# loop till the search space is exhausted
while left <= right:
# if nums[left…right] consists of only one element, update its count
if nums[left] == nums[right]:
freq[nums[left]] = freq.get(nums[left], 0) + (right - left + 1)
# now discard nums[left…right] and continue searching in
# nums[right+1… n-1] for nums[left]
left = right + 1
right = len(nums) - 1
else:
# reduce the search space
right = (left + right) // 2
return freq
if __name__ == ‘__main__’:
nums = [2, 2, 2, 4, 4, 4, 5, 5, 6, 8, 8, 9] print(findFrequency(nums)) \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ recursive approach:
# Function to find the frequency of each element in a sorted list def findFrequency(nums, left, right, freq):
if left > right:
return
# if every element in sublist nums[left…right] is equal,
# then increment the element's count by `n`
if nums[left] == nums[right]:
count = freq.get(nums[left])
if count is None:
count = 0
freq[nums[left]] = count + (right - left + 1)
return
mid = (left + right) // 2
# divide the list into left and right sublist and recur
findFrequency(nums, left, mid, freq)
findFrequency(nums, mid + 1, right, freq)
if __name__ == ‘__main__’:
nums = [2, 2, 2, 4, 4, 4, 5, 5, 6, 8, 8, 9]
# find the frequency of each element in the list and store it in a dictionary
freq = {}
findFrequency(nums, 0, len(nums) - 1, freq)
print(freq)
