"""
Climbing Staircase
There exists a staircase with N steps, and you can climb up either X different steps at a time.
Given N, write a function that returns the number of unique ways you can climb the staircase.
The order of the steps matters.
Input: steps = [1, 2], height = 4
Output: 5
Output explanation:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
=========================================
Dynamic Programing solution.
Time Complexity: O(N*S)
Space Complexity: O(N)
"""
############
# Solution #
############
def climbing_staircase(steps, height):
dp = [0 for i in range(height)]
# add all steps into dp
for s in steps:
if s <= height:
dp[s - 1] = 1
# for each position look how you can arrive there
for i in range(height):
for s in steps:
if i - s >= 0:
dp[i] += dp[i - s]
return dp[height - 1]
###########
# Testing #
###########
# Test 1
# Correct result => 5
print(climbing_staircase([1, 2], 4))
# Test 2
# Correct result => 3
print(climbing_staircase([1, 3, 5], 4))
"""
Coin Change
You are given coins of different denominations and a total amount of money amount.
Write a function to compute the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.
Input: coins = [1, 2, 5], amount = 11
Output: 3
Input: coins = [2], amount = 3
Output: -1
=========================================
Dynamic programming solution 1
Time Complexity: O(A*C) , A = amount, C = coins
Space Complexity: O(A)
Dynamic programming solution 2 (don't need the whole array, just use modulo to iterate through the partial array)
Time Complexity: O(A*C) , A = amount, C = coins
Space Complexity: O(maxCoin)
"""
##############
# Solution 1 #
##############
def coin_change_1(coins, amount):
if amount == 0:
return 0
if len(coins) == 0:
return -1
max_value = amount + 1 # use this instead of math.inf
dp = [max_value for i in range(max_value)]
dp[0] = 0
for i in range(1, max_value):
for c in coins:
if c <= i:
# search on previous positions for min coins needed
dp[i] = min(dp[i], dp[i - c] + 1)
if dp[amount] == max_value:
return -1
return dp[amount]
##############
# Solution 2 #
##############
def coin_change_2(coins, amount):
if amount == 0:
return 0
if len(coins) == 0:
return -1
max_value = amount + 1
max_coin = min(max_value, max(coins) + 1)
dp = [max_value for i in range(max_coin)]
dp[0] = 0
for i in range(1, max_value):
i_mod = i % max_coin
dp[i_mod] = max_value # reset current position
for c in coins:
if c <= i:
# search on previous positions for min coins needed
dp[i_mod] = min(dp[i_mod], dp[(i - c) % max_coin] + 1)
if dp[amount % max_coin] == max_value:
return -1
return dp[amount % max_coin]
###########
# Testing #
###########
# Test 1
# Correct result => 3
coins = [1, 2, 5]
amount = 11
print(coin_change_1(coins, amount))
print(coin_change_2(coins, amount))
# Test 2
# Correct result => -1
coins = [2]
amount = 3
print(coin_change_1(coins, amount))
print(coin_change_2(coins, amount))
"""
Count IP Addresses
An IP Address (IPv4) consists of 4 numbers which are all between 0 and 255.
In this problem however, we are dealing with 'Extended IP Addresses' which consist of K such numbers.
Given a string S containing only digits and a number K,
your task is to count how many valid 'Extended IP Addresses' can be formed.
An Extended IP Address is valid if:
* it consists of exactly K numbers
* each numbers is between 0 and 255, inclusive
* a number cannot have leading zeroes
Input: '1234567', 3
Output: 1
Output explanation: Valid IP addresses: '123.45.67'.
Input: '100111', 3
Output: 1
Output explanation: Valid IP addresses: '100.1.11', '100.11.1', '10.0.111'.
Input: '345678', 2
Output: 0
Output explanation: It is not possible to form a valid IP Address with two numbers.
=========================================
1D Dynamic programming solution.
Time Complexity: O(N*K)
Space Complexity: O(N)
"""
############
# Solution #
############
def count_ip_addresses(S, K):
n = len(S)
if n == 0:
return 0
if n < K:
return 0
dp = [0] * (n + 1)
dp[0] = 1
for i in range(K):
# if you want to save just little calculations you can use min(3*(i+1), n) instead of n
for j in range(n, i, -1):
# reset the value
dp[j] = 0
# use iteration to check all 3 possible numbers (x, xx, xxx), instead of writing 3 IFs
for e in range(max(i, j - 3), j):
if is_valid(S[e:j]):
dp[j] += dp[e]
return dp[n]
def is_valid(S):
if (len(S) > 1) and (S[0] == "0"):
return False
return int(S) <= 255
###########
# Testing #
###########
# Test 1
# Correct result => 1
print(count_ip_addresses("1234567", 3))
# Test 2
# Correct result => 3
print(count_ip_addresses("100111", 3))
# Test 3
# Correct result => 0
print(count_ip_addresses("345678", 2))
"""
Create Palindrome (Minimum Insertions to Form a Palindrome)
Given a string, find the palindrome that can be made by inserting the fewest number of characters as possible anywhere in the word.
If there is more than one palindrome of minimum length that can be made, return the lexicographically earliest one (the first one alphabetically).
Input: 'race'
Output: 'ecarace'
Output explanation: Since we can add three letters to it (which is the smallest amount to make a palindrome).
There are seven other palindromes that can be made from "race" by adding three letters, but "ecarace" comes first alphabetically.
Input: 'google'
Output: 'elgoogle'
Input: 'abcda'
Output: 'adcbcda'
Output explanation: Number of insertions required is 2 - aDCbcda (between the first and second character).
Input: 'adefgfdcba'
Output: 'abcdefgfedcba'
Output explanation: Number of insertions required is 3 i.e. aBCdefgfEdcba.
=========================================
Recursive count how many insertions are needed, very slow and inefficient.
Time Complexity: O(2^N)
Space Complexity: O(N^2) , for each function call a new string is created (and the recursion can have depth of max N calls)
Dynamic programming. Count intersections looking in 3 direction in the dp table (diagonally left-up or min(left, up)).
Time Complexity: O(N^2)
Space Complexity: O(N^2)
"""
##############
# Solution 1 #
##############
def create_palindrome_1(word):
n = len(word)
# base cases
if n == 1:
return word
if n == 2:
if word[0] != word[1]:
word += word[0] # make a palindrom
return word
# check if the first and last chars are same
if word[0] == word[-1]:
# add first and last chars
return word[0] + create_palindrome_1(word[1:-1]) + word[-1]
# if not remove the first and after that the last char
# and find which result has less chars
first = create_palindrome_1(word[1:])
first = word[0] + first + word[0] # add first char twice
last = create_palindrome_1(word[:-1])
last = word[-1] + last + word[-1] # add last char twice
if len(first) < len(last):
return first
return last
##############
# Solution 2 #
##############
import math
def create_palindrome_2(word):
n = len(word)
dp = [[0 for j in range(n)] for i in range(n)]
# run dp
for gap in range(1, n):
left = 0
for right in range(gap, n):
if word[left] == word[right]:
dp[left][right] = dp[left + 1][right - 1]
else:
dp[left][right] = min(dp[left][right - 1], dp[left + 1][right]) + 1
left += 1
# build the palindrome using the dp table
return build_palindrome(word, dp, 0, n - 1)
def build_palindrome(word, dp, left, right):
# similar like the first solution, but without exponentialy branching
# this is linear time, we already know the inserting values
if left > right:
return ""
if left == right:
return word[left]
if word[left] == word[right]:
return word[left] + build_palindrome(word, dp, left + 1, right - 1) + word[left]
if dp[left + 1][right] < dp[left][right - 1]:
return word[left] + build_palindrome(word, dp, left + 1, right) + word[left]
return word[right] + build_palindrome(word, dp, left, right - 1) + word[right]
###########
# Testing #
###########
# Test 1
# Correct result => 'ecarace'
word = "race"
print(create_palindrome_1(word))
print(create_palindrome_2(word))
# Test 2
# Correct result => 'elgoogle'
word = "google"
print(create_palindrome_1(word))
print(create_palindrome_2(word))
# Test 3
# Correct result => 'adcbcda'
word = "abcda"
print(create_palindrome_1(word))
print(create_palindrome_2(word))
# Test 4
# Correct result => 'abcdefgfedcba'
word = "adefgfdcba"
print(create_palindrome_1(word))
print(create_palindrome_2(word))
"""
Interleaving Strings
Given are three strings A, B and C.
C is said to be interleaving of A and B, if:
- it contains all characters of A and B, and
- order of all characters from A and B is preserved in C
Your task is to count in how many ways C can be formed by interleaving of A and B.
Input: A='xy', B= 'xz', C: 'xxyz'
Output: 2
Output explanation:
1) Take 'x' from A, then 'x' from B, then 'y' from A and at the end 'z' from B.
2) Take 'x' from B, then 'x' from A, then 'y' from A and at the end 'z' from B.
=========================================
2D Dynamic programming solution.
Time Complexity: O(N*M)
Space Complexity: O(N*M)
1D Dynamic programming solution. Only the last two rows from the whole matrix are used, but that could be represented using only 1 row.
Time Complexity: O(N*M)
Space Complexity: O(M)
"""
##############
# Solution 1 #
##############
def interleaving_strings_1(A, B, C):
nA, nB, nC = len(A), len(B), len(C)
if nA + nB != nC:
return 0
dp = [[0 for j in range(nB + 1)] for i in range(nA + 1)]
# starting values
dp[0][0] = 1
for i in range(1, nA + 1):
if A[i - 1] == C[i - 1]:
# short form of if A[i - 1] == C[i - 1] and dp[i - 1][0] == 1
# dp[i][0] and dp[0][1] can be only 0 or 1
dp[i][0] = dp[i - 1][0]
for i in range(1, nB + 1):
if B[i - 1] == C[i - 1]:
dp[0][i] = dp[0][i - 1]
# run dp
for i in range(1, nA + 1):
for j in range(1, nB + 1):
if A[i - 1] == C[i + j - 1]:
# look for the dp value from the previous position
dp[i][j] += dp[i - 1][j]
if B[j - 1] == C[i + j - 1]:
# look for the dp value from the previous position
dp[i][j] += dp[i][j - 1]
return dp[nA][nB]
##############
# Solution 2 #
##############
def interleaving_strings_2(A, B, C):
nA, nB, nC = len(A), len(B), len(C)
if nA + nB != nC:
return 0
dp = [0 for j in range(nB + 1)]
# starting values
dp[0] = 1
for i in range(1, nB + 1):
if B[i - 1] == C[i - 1]:
dp[i] = dp[i - 1]
# run dp
for i in range(1, nA + 1):
if A[i - 1] != C[i - 1]:
# reset the value
dp[0] = 0
for j in range(1, nB + 1):
if A[i - 1] != C[i + j - 1]:
# reset the value
dp[j] = 0
if B[j - 1] == C[i + j - 1]:
dp[j] += dp[j - 1]
return dp[nB]
###########
# Testing #
###########
# Test 1
# Correct result => 2
a, b, c = "xy", "xz", "xxyz"
print(interleaving_strings_1(a, b, c))
print(interleaving_strings_2(a, b, c))
"""
Jump Game 2
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Input: XXX
Output: XXX
Output explanation: XXX
=========================================
Classical 1D Dynamic Programming solution.
Time Complexity: O(N) , maybe looks like O(N^2) but that's not possible
Space Complexity: O(N)
If you analyze the previous solution, you'll see that you don't need the whole DP array.
Time Complexity: O(N)
Space Complexity: O(1)
"""
##############
# Solution 1 #
##############
def min_jumps_1(nums):
n = len(nums)
if n <= 1:
return 0
dp = [-1] * n
dp[0] = 0
for i in range(n):
this_jump = i + nums[i]
jumps = dp[i] + 1
if this_jump >= n - 1:
return jumps
# starging from back, go reverse and
# change all -1 values and break when first positive is found
for j in range(this_jump, i, -1):
if dp[j] != -1:
break
dp[j] = jumps
##############
# Solution 2 #
##############
def min_jumps_2(nums):
n = len(nums)
if n <= 1:
return 0
jumps = 0
max_jump = 0
new_max_jump = 0
for i in range(n):
if max_jump < i:
max_jump = new_max_jump
jumps += 1
this_jump = i + nums[i]
if this_jump >= n - 1:
return jumps + 1
new_max_jump = max(new_max_jump, this_jump)
###########
# Testing #
###########
# Test 1
# Correct result => 2
nums = [2, 3, 1, 1, 4]
print(min_jumps_1(nums))
print(min_jumps_2(nums))
"""
Longest Common Subsequence
Given 2 strings, find the longest common subseqence - https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
NOT Longest Common Substring, this is a different problem.
Substring is a string composed ONLY of neighboring chars, subsequence could contain non-neighboring chars.
Input: 'ABAZDC', 'BACBAD'
Output: 'ABAD'
Input: 'I'm meto', 'I am Meto'
Output: 'Im eto'
=========================================
Dynamic programming solution.
Find more details here: https://www.geeksforgeeks.org/printing-longest-common-subsequence/
Time Complexity: O(N * M)
Space Complexity: O(N * M) , can be O(M) see longest_common_substring.py solution (but you'll need to save subsequences)
"""
############
# Solution #
############
def longest_common_subsequence(str1, str2):
n, m = len(str1), len(str2)
# create dp matrix
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
# run dp
for i in range(1, n + 1):
for j in range(1, m + 1):
# checks only in 3 directions in the table
# in short: to the current position dp could come from those 3 previous positions
# ^ ^
# \ |
# <- O
if str1[i - 1] == str2[j - 1]:
# from this position dp could come only if there is a match in the previous chars
dp[i][j] = dp[i - 1][j - 1] + 1
else:
# dp could come from these positions only if there is no much
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# find the subseqence/string
letters = dp[n][m]
# use an array for storing the chars because string manipulation operations are not time and space efficient
result = ["" for i in range(letters)]
i = n
j = m
while (i != 0) and (j != 0):
# use the inverse logic from upper code (filling the dp table)
if str1[i - 1] == str2[j - 1]:
letters -= 1
result[letters] = str1[i - 1]
j -= 1
i -= 1
elif dp[i - 1][j] < dp[i][j - 1]:
j -= 1
else:
i -= 1
return "".join(result)
###########
# Testing #
###########
# Test 1
# Correct result => 'ABAD'
print(longest_common_subsequence("ABAZDC", "BACBAD"))
# Test 2
# Correct result => 'Im eto'
print(longest_common_subsequence("I'm meto", "I am Meto"))
"""
Longest Common Substring
Given two strings X and Y, find the of longest common substring.
Input: 'GeeksforGeeks', 'GeeksQuiz'
Output: 'Geeks'
=========================================
Dynamic Programming Solution.
Time Complexity: O(N * M)
Space Complexity: O(M)
* For this problem exists a faster solution, using Suffix tree, Time Complexity O(N + M).
"""
############
# Solution #
############
def longest_common_substring(str1, str2):
n, m = len(str1), len(str2)
# instead of creating a whole dp table, use only 2 rows (current and previous row)
curr = [0 for j in range(m + 1)]
prev = []
max_length = 0
max_idx = 0
for i in range(1, n + 1):
# save the previous row and create the current row
prev = curr
curr = [0 for j in range(m + 1)]
for j in range(1, m + 1):
if str1[i - 1] == str2[j - 1]:
# search only for matching chars
curr[j] = prev[j - 1] + 1
if curr[j] > max_length:
# save the last matching index of the first string
max_length = curr[j]
max_idx = i
return str1[max_idx - max_length : max_idx]
###########
# Testing #
###########
# Test 1
# Correct result => BABC
print(longest_common_substring("ABABC", "BABCA"))
# Test 2
# Correct result => Geeks
print(longest_common_substring("GeeksforGeeks", "GeeksQuiz"))
# Test 3
# Correct result => abcd
print(longest_common_substring("abcdxyz", "xyzabcd"))
# Test 4
# Correct result => abcdez
print(longest_common_substring("zxabcdezy", "yzabcdezx"))
"""
Longest Increasing Subsequence (LIS)
Find the longest increasing subsequence.
(subsequence doesn't mean that all elements need to be neighboring in the original array).
Sample input: [1, 4, 2, 0, 3, 1]
Sample output: [1, 2, 3]
or output the length
Sample output: 3
=========================================
Dynamic programming (classical) solution.
Time Complexity: O(N^2)
Space Complexity: O(N)
Dynamic programing in combination with binary search.
Explanation in details: https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
Time Complexity: O(N * logN)
Space Complexity: O(N^2) , if you need only the length of the LIS, extra space complexity will be O(N)
"""
##############
# Solution 1 #
##############
def longest_increasing_subsequence_1(nums):
n = len(nums)
if n == 0:
return 0
dp = [1 for i in range(n)]
max_val = 1
# run dp
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
max_val = max(max_val, dp[i])
# find the values (there could be more combinations/solutions)
current_val = max_val
result = [0 for i in range(current_val)]
# start from the back and look for the biggest value in dp list
for i in range(n - 1, -1, -1):
if (dp[i] == current_val) and (
(len(result) == current_val) or (result[current_val] > nums[i])
):
current_val -= 1
result[current_val] = nums[i]
return result
##############
# Solution 2 #
##############
def longest_increasing_subsequence_2(nums):
n = len(nums)
if n == 0:
return 0
# the last dp array result in longest increasing subsequence
dp = []
for i in range(n):
idx = binary_search(dp, nums[i])
k = len(dp)
if idx == k:
# bigger element than the current wasn't found
arr = []
if k != 0:
arr = [i for i in dp[-1]] # make a copy
arr.append(nums[i])
dp.append(arr)
elif dp[idx][-1] > nums[i]:
# smaller element was found, replace it
dp[idx][-1] = nums[i]
return dp[-1]
def binary_search(dp, target):
l = 0
r = len(dp) - 1
while l <= r:
mid = l + (r - l) // 2
if dp[mid][-1] == target:
return mid
elif dp[mid][-1] < target:
l = mid + 1
else:
r = mid - 1
return l
###########
# Testing #
###########
# Test 1
# Correct result => [2, 3, 7, 18] - one of the possible combinations
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
# Test 2
# Correct result => [1, 2, 3]
arr = [1, 2, 3]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
# Test 3
# Correct result => [1, 2, 5, 7, 12] - one of the possible combinations
arr = [10, 1, 3, 8, 2, 0, 5, 7, 12, 3]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
# Test 4
# Correct result => [1, 2, 3, 4, 5, 6]
arr = [12, 1, 11, 2, 10, 3, 9, 4, 8, 5, 7, 6]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
# Test 5
# Correct result => [1, 2, 3]
arr = [1, 4, 2, 0, 3, 1]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
# Test 6
# Correct result => [3] - one of the possible combinations
arr = [7, 5, 5, 5, 5, 5, 3]
print(longest_increasing_subsequence_1(arr))
print(longest_increasing_subsequence_2(arr))
"""
Max Profit With K Transactions
You are given an array of integers representing the prices of a single stock on various days
(each index in the array represents a different day).
You are also given an integer k, which represents the number of transactions you are allowed to make.
One transaction consists of buying the stock on a given day and selling it on another, later day.
Write a function that returns the maximum profit that you can make buying and selling the stock,
given k transactions. Note that you can only hold 1 share of the stock at a time; in other words,
you cannot buy more than 1 share of the stock on any given day, and you cannot buy a share of the
stock if you are still holding another share.
In a day, you can first sell a share and buy another after that.
Input: [5, 11, 3, 50, 60, 90], 2
Output: 93
Output explanation: Buy 5, Sell 11; Buy 3, Sell 90
=========================================
Optimized dynamic programming solution.
For this solution you'll need only the current and previous rows.
The original (not optimized) DP formula is: MAX(dp[t][d-1], price[d] + MAX(dp[t-1][x] - price[x])),
but this is O(K * N^2) Time Complexity, and O(N * K) space complexity.
Time Complexity: O(N * К)
Space Complexity: O(N)
"""
############
# Solution #
############
import math
def max_profit_with_k_transactions(prices, k):
days = len(prices)
if days < 2:
# not enough days for a transaction
return 0
# transaction = buy + sell (2 separate days)
# in a day you can sell and after that buy a share
# (according to this, can't exists more transactions than the number of the prices/days)
k = min(k, days)
# create space optimized dp matrix
dp = [[0 for j in range(days)] for i in range(2)]
for t in range(k):
max_prev = -math.inf
# compute which row is previous and which is the current one
prev_idx = (t - 1) % 2
curr_idx = t % 2
# the values in dp table for these days will be same
# just ignore them, don't update them (because those combinations were tried)
past_days = t
# only save the last one
dp[curr_idx][past_days] = dp[prev_idx][past_days]
for d in range(past_days + 1, days):
# first try to buy with the current price
max_prev = max(max_prev, dp[prev_idx][d - 1] - prices[d - 1])
# after that try to sell with the current price
dp[curr_idx][d] = max(dp[curr_idx][d - 1], max_prev + prices[d])
# return the last value from the last transaction
return dp[(k - 1) % 2][-1]
###########
# Testing #
###########
# Test 1
# Correct result => 9
print(max_profit_with_k_transactions([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10))
# Test 2
# Correct result => 93
print(max_profit_with_k_transactions([5, 11, 3, 50, 60, 90], 2))
"""
Maximum subarray sum
The subarray must be contiguous.
Sample input: [-2, -3, 4, -1, -2, 1, 5, -3]
Sample output: 7
Output explanation: [4, -1, -2, 1, 5]
=========================================
Need only one iteration, in each step add the current element to the current sum.
When the sum is less than 0, reset the sum to 0 and continue with adding. (we care only about non-negative sums)
After each addition, check if the current sum is greater than the max sum. (Called Kadane's algorithm)
Time Complexity: O(N)
Space Complexity: O(1)
"""
############
# Solution #
############
def max_subarray_sum(a):
curr_sum = 0
max_sum = 0
for val in a:
# extend the current sum with the curren value;
# reset it to 0 if it is smaller than 0, we care only about non-negative sums
curr_sum = max(0, curr_sum + val)
# check if this is the max sum
max_sum = max(max_sum, curr_sum)
return max_sum
###########
# Testing #
###########
# Test 1
# Correct result => 7
print(max_subarray_sum([-2, -3, 4, -1, -2, 1, 5, -3]))
# Test 2
# Correct result => 5
print(max_subarray_sum([1, -2, 2, -2, 3, -2, 4, -5]))
# Test 3
# Correct result => 7
print(max_subarray_sum([-2, -5, 6, -2, -3, 1, 5, -6]))
# Test 4
# Correct result => 0
print(max_subarray_sum([-6, -1]))
"""
Min Cost Coloring
A builder is looking to build a row of N houses that can be of K different colors.
He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.
Given an N by K matrix where the nth row and kth column represents the cost to build the
nth house with kth color, return the minimum cost which achieves this goal.
=========================================
Dynamic programming, for each house search for the cheapest combination of the previous houses.
But don't search the whole array with combinations (colors), save only the smallest 2
(in this case we're sure that the previous house doesn't have the same color).
Time Complexity: O(N * K)
Space Complexity: O(1)
"""
############
# Solution #
############
import math
def min_cost_coloring(dp):
# no need from a new dp matrix, you can use the input matrix
n = len(dp)
if n == 0:
return 0
m = len(dp[0])
if m < 2:
return -1
# save only the smallest 2 costs instead of searching the whole previous array
prev_min = [(0, -1), (0, -1)]
for i in range(n):
curr_min = [(math.inf, -1), (math.inf, -1)]
for j in range(m):
# find result with different color
if j != prev_min[0][1]:
dp[i][j] += prev_min[0][0]
else:
dp[i][j] += prev_min[1][0]
# save the current result if smaller than the current 2
if curr_min[0][0] > dp[i][j]:
curr_min[1] = curr_min[0]
curr_min[0] = (dp[i][j], j)
elif curr_min[1][0] > dp[i][j]:
curr_min[1] = (dp[i][j], j)
prev_min = curr_min
# return the min cost of the last house
return min(dp[n - 1])
###########
# Testing #
###########
# Test 1
# Correct result => 5
print(
min_cost_coloring(
[[1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 2, 1, 4, 5], [3, 2, 1, 4, 3]]
)
)
# Test 2
# Correct result => 6
print(
min_cost_coloring(
[[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]
)
)
"""
Number of Decodings
Given the mapping a=1, b=2, ... , z=26, and an encoded message, count the number of ways it can be decoded.
For example, the message "111" would give 3, since it could be decoded as "aaa", "ka" and "ak".
All of the messages are decodable!
=========================================
The easiest solution is Brute-Force (building a tree and making all combinations),
and in the worst case there will be Fibbionaci(N) combinations, so the worst Time Complexity will be O(Fib(N))
Dynamic programming solution. Similar to number_of_smses.py.
Time Complexity: O(N)
Space Complexity: O(N)
"""
############
# Solution #
############
def num_decodings(code):
n = len(code)
dp = [0 for i in range(n)]
if n == 0:
return 0
dp[0] = 1
if n == 1:
return dp[0]
dp[1] = (code[1] != "0") + is_valid(code[0:2])
for i in range(2, n):
if code[i] != "0":
# looking for how many combinations are there till now if this is a single digit
dp[i] += dp[i - 1]
if is_valid(code[i - 1 : i + 1]):
# looking for how many combinations are there till now if this is a number of 2 digits
dp[i] += dp[i - 2]
return dp[n - 1]
def is_valid(code):
k = int(code)
return (k < 27) and (k > 9)
###########
# Testing #
###########
# Test 1
# Correct result => 5
print(num_decodings("12151"))
# Test 2
# Correct result => 5
print(num_decodings("1111"))
# Test 3
# Correct result => 3
print(num_decodings("111"))
# Test 4
# Correct result => 1
print(num_decodings("1010"))
# Test 5
# Correct result => 4
print(num_decodings("2626"))
# Test 6
# Correct result => 1
print(num_decodings("1"))
# Test 7
# Correct result => 2
print(num_decodings("11"))
# Test 8
# Correct result => 3
print(num_decodings("111"))
# Test 9
# Correct result => 5
print(num_decodings("1111"))
# Test 10
# Correct result => 8
print(num_decodings("11111"))
# Test 11
# Correct result => 13
print(num_decodings("111111"))
# Test 12
# Correct result => 21
print(num_decodings("1111111"))
# Test 13
# Correct result => 34
print(num_decodings("11111111"))
"""
Number of SMSes
Given the number sequence that is being typed in order to write and SMS message, return the count
of all the possible messages that can be constructed.
1 2 3
abc def
4 5 6
ghi jkl mno
7 8 9
pqrs tuv wxyz
The blank space character is constructed with a '0'.
Input: '222'
Output: 4
Output explanation: '222' could mean: 'c', 'ab','ba' or 'aaa'. That makes 4 possible messages.
=========================================
Dynamic programming solution. Similar to number_of_decodings.py.
Time Complexity: O(N)
Space Complexity: O(N)
"""
############
# Solution #
############
def num_smses(sequence):
n = len(sequence)
dp = [0] * n
# dp starting values, check all 4 possible starting combinations
for i in range(min(4, n)):
if is_valid(sequence[0 : i + 1]):
dp[i] = 1
# run dp
for i in range(1, n):
# check all 4 possible combinations (x, xx, xxx, xxxx)
for j in range(min(4, i)):
if is_valid(sequence[i - j : i + 1]):
dp[i] += dp[i - j - 1]
return dp[n - 1]
def is_valid(sequence):
ch = sequence[0]
for c in sequence:
if c != ch:
return False
if sequence == "0":
return True
if ((ch >= "2" and ch <= "6") or ch == "8") and (len(sequence) < 4):
return True
if (ch == "7") or (ch == "9"):
return True
return False
###########
# Testing #
###########
# Test 1
# Correct result => 4
print(num_smses("222"))
# Test 2
# Correct result => 14
print(num_smses("2202222"))
# Test 3
# Correct result => 274
print(num_smses("2222222222"))
"""
Ordered Digits
We are given a number and we need to transform to a new number where all its digits are ordered in a non descending order.
We are allowed to increase or decrease a digit by 1, and each of those actions counts as one operation.
We are also allowed to over/underflow a number meaning from '9' we can change to '0' and also from '0' to '9', also costing only one operation.
One same digit can be changed multiple times.
Find the minimum number of operations we need to do do to create a new number with its ordered digits.
Input: 301
Output: 3
Output explanation: 301 -> 201 -> 101 -> 111, in this case 3 operations are required to get an ordered number.
Input: 901
Output: 1
Output explanation: 901 -> 001, in this case 1 operation is required to get an ordered number.
Input: 5982
Output: 4
Output explanation: 5982 -> 5981 -> 5980 -> 5989 -> 5999, in this case 4 operations are required to get an ordered number.
=========================================
Dynamic programming solution. For each position, calculate the cost of transformation to each possible digit (0-9).
And take the minimum value from the previous position (but smaller than the current digit).
Time Complexity: O(N) , O(N*10) = O(N), N = number of digits
Space Complexity: O(N) , same O(N*2) = O(N)
"""
############
# Solution #
############
def ordered_digits(number):
n = len(number)
dp = [[0 for j in range(10)] for i in range(2)]
for i in range(n):
min_prev = float("inf")
for j in range(10):
# find the min value from the previous digit and add it to the current value
min_prev = min(min_prev, dp[(i - 1) % 2][j])
# compute diff between the current digit and wanted digit
diff = abs(j - int(number[i]))
dp[i % 2][j] = min(diff, 10 - diff) + min_prev
# min value from the last digit
return min(dp[(n - 1) % 2])
###########
# Testing #
###########
# Test 1
# Correct result => 3
print(ordered_digits("301"))
# Test 2
# Correct result => 1
print(ordered_digits("901"))
# Test 3
# Correct result => 4
print(ordered_digits("5982"))
"""
Split Coins
You have a number of coins with various amounts.
You need to split the coins in two groups so that the difference between those groups in minimal.
Input: [1, 1, 1, 3, 5, 10, 18]
Output: 1
Output explanation: First group 1, 3, 5, 10 (or 1, 1, 3, 5, 10) and second group 1, 1, 18 (or 1, 18).
=========================================
Simple dynamic programming solution. Find the closest sum to the half of the sum of all coins.
Time Complexity: O(C*HS) , C = number of coins, HS = half of the sum of all coins
Space Complexity: O(HS)
"""
############
# Solution #
############
def split_coins(coins):
if len(coins) == 0:
return -1
full_sum = sum(coins)
half_sum = full_sum // 2 + 1
dp = [False] * half_sum
dp[0] = True
for c in coins:
for i in range(half_sum - 1, -1, -1):
if (i >= c) and dp[i - c]:
# if you want to find coins, save the coin here dp[i] = c
dp[i] = True
for i in range(half_sum - 1, -1, -1):
if dp[i]:
# if you want to print coins, while i>0: print(dp[i]) i -= dp[i]
return full_sum - 2 * i
# not possible
return -1
###########
# Testing #
###########
# Test 1
# Correct result => 1
print(split_coins([1, 1, 1, 3, 5, 10, 18]))
"""
Sum of non-adjacent numbers
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers.
Numbers can be 0 or negative.
Input: [2, 4, 6, 2, 5]
Output: 13
Output explanation: We pick 2, 6, and 5.
Input: [5, 1, 1, 5]
Output: 10
Output explanation: We pick 5 and 5.
=========================================
Dynamic programming solution, but don't need the whole DP array, only the last 3 sums (DPs) are needed.
Time Complexity: O(N)
Space Complexity: O(1)
"""
############
# Solution #
############
def sum_non_adjacent(arr):
n = len(arr)
# from the dp matrix you only need the last 3 sums
sums = [0, 0, 0]
# TODO: refactor these if-elses, those are to skip using of DP matrix
if n == 0:
return 0
# if negative or zero, the sum will be 0
sums[0] = max(arr[0], 0)
if n == 1:
return sums[0]
sums[1] = arr[1]
# if the second number is negative or zero, then jump it
if sums[1] <= 0:
sums[1] = sums[0]
if n == 2:
return max(sums[0], sums[1])
sums[2] = arr[2]
# if the third number is negative or zero, then jump it
if sums[2] <= 0:
sums[2] = max(sums[0], sums[1])
else:
sums[2] += sums[0]
# THE SOLUTION
for i in range(3, n):
temp = 0
if arr[i] > 0:
# take this number, because it's positive and the sum will be bigger
temp = max(sums[0], sums[1]) + arr[i]
else:
# don't take this number, because the sum will be same or smaller
temp = max(sums)
# remove the first sum
sums = sums[1:] + [temp]
# return the max sum
return max(sums)
###########
# Testing #
###########
# Test 1
# Correct result => 13
print(sum_non_adjacent([2, 4, 6, 2, 5]))
# Test 2
# Correct result => 15
print(sum_non_adjacent([2, 4, 2, 6, 2, -3, -2, 0, -3, 5]))
# Test 3
# Correct result => 10
print(sum_non_adjacent([5, 1, 1, 5]))
# Test 4
# Correct result => 10
print(sum_non_adjacent([5, 1, -1, 1, 5]))
"""
Transform Number Ascending Digits
Given a number and we need to transform to a new number where all its digits are ordered in a non descending order.
All digits can be increased, decreased, over/underflow are allowed.
Find the minimum number of operations we need to do to create a new number with its ordered digits.
Input: '5982'
Output: 4
Output explanation: 5999, 1 operation to transform 8 to 9, 3 operations to transform 2 to 9.
=========================================
Dynamic programming solution.
Time Complexity: O(N) , O(N * 10 * 10) = O(100 N) = O(N)
Space Complexity: O(1) , O(10 * 10) = O(100) = O(1)
"""
############
# Solution #
############
def operations(number):
n = len(number)
diff = lambda i, j: abs(j - int(number[i]))
# compute diff between the current digit and wanted digit, and fill the dp
prev_dp = [min(diff(0, i), 10 - diff(0, i)) for i in range(10)]
# go through all digits and see all possible combinations using dynamic programming
for i in range(1, n):
curr_dp = [min(diff(i, j), 10 - diff(i, j)) for j in range(10)]
for j in range(10):
# find the min value for the previous digit and add it to the current value
curr_dp[j] += min(prev_dp[0 : j + 1])
prev_dp = curr_dp
# min value from the last digit
min_dist = min(prev_dp)
return min_dist
###########
# Testing #
###########
# Test 1
# Correct result => 1
print(operations("901"))
# Test 2
# Correct result => 3
print(operations("301"))
# Test 3
# Correct result => 4
print(operations("5982"))
"""
Word Break (Find the original words)
Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list.
If there is more than one possible reconstruction, return solution with less words.
If there is no possible reconstruction, then return null.
Input: sentence = 'thequickbrownfox', words = ['quick', 'brown', 'the', 'fox']
Output: ['the', 'quick', 'brown', 'fox']
Input: sentence = 'bedbathandbeyond', words = ['bed', 'bath', 'bedbath', 'and', 'beyond']
Output: ['bedbath', 'and', 'beyond'] (['bed', 'bath', 'and', 'beyond] has more words)
=========================================
Optimized dynamic programming solution (more simpler solutions can be found here https://www.geeksforgeeks.org/word-break-problem-dp-32/)
Time Complexity: O(N*M) , N = number of chars in the sentence, M = max word length
Space Complexity: O(N+W) , W = number of words
Bonus solution: Backtracking, iterate the sentence construct a substring and check if that substring exist in the set of words.
If the end is reached but the last word doesn't exist in the words, go back 1 word from the result (backtracking).
* But this solution doesn't give the result with the smallest number of words (gives the first found result)
Time Complexity: O(?) , (worst case, about O(W! * N), for example sentence='aaaaaac', words=['a','aa','aaa','aaaa','aaaaa', 'aaaaaa'])
Space Complexity: O(W)
"""
############
# Solution #
############
import math
def word_break(sentence, words):
n, w = len(sentence), len(words)
if (n == 0) or (w == 0):
return None
dw = [-1 for i in range(n + 1)]
dp = [math.inf for i in range(n + 1)]
dp[0] = 0
matched_indices = [0]
dic = {} # save all words in dictionary for faster searching
max_word = 0 # length of the max word
for i in range(w):
dic[words[i]] = i
max_word = max(max_word, len(words[i]))
for i in range(1, n + 1):
matched = False
# start from the back of the matched_indices list (from the bigger numbers)
for j in range(len(matched_indices) - 1, -1, -1):
matched_index = matched_indices[j]
# break this loop if the subsentence created with this matched index is bigger than the biggest word
if matched_index < i - max_word:
break
subsentence = sentence[matched_index:i]
# save this result if this subsentence exist in the words and number of words that forms sentence is smaller
if (subsentence in dic) and (dp[matched_index] + 1 < dp[i]):
dp[i] = dp[matched_index] + 1
dw[i] = dic[subsentence]
matched = True
if matched:
matched_indices.append(i)
# the sentence can't be composed from the given words
if dp[n] == math.inf:
return None
# find the words that compose this sentence
result = ["" for i in range(dp[n])]
i = n
j = dp[n] - 1
while i > 0:
result[j] = words[dw[i]]
i -= len(words[dw[i]])
j -= 1
return result
#########################
# Solution Backtracking #
#########################
from collections import deque
def word_break_backtracking(sentence, words):
all_words = set()
# create a set from all words
for i in range(len(words)):
all_words.add(words[i])
n = len(sentence)
i = 0
subsentence = ""
result = deque()
# go letter by letter and save the new letter in subsentence
while (i < n) or (len(subsentence) != 0):
# if there are no left letters in the sentence, then this combination is not valid
# remove the last word from the results and continue from that word
if i == n:
i -= len(subsentence)
# if there are no words in the result, then this string is not composed only from the given words
if len(result) == 0:
return None
subsentence = result[-1]
result.pop()
# add the new letter into subsentence and remove it from the sentence
subsentence += sentence[i]
i += 1
# check if the new word exist in the set
if subsentence in all_words:
result.append(subsentence)
subsentence = ""
return list(result)
###########
# Testing #
###########
# Test 1
# Correct result => ['the', 'quick', 'brown', 'fox']
print(word_break("thequickbrownfox", ["quick", "brown", "the", "fox"]))
# Test 2
# Correct result => ['bedbath', 'and', 'beyond']
print(word_break("bedbathandbeyond", ["bed", "bath", "bedbath", "and", "beyond"]))
# Test 3
# Correct result => ['bedbath', 'andbeyond']
print(
word_break(
"bedbathandbeyond",
["bed", "and", "bath", "bedbath", "bathand", "beyond", "andbeyond"],
)
)
# Test 4
# Correct result => None ('beyo' doesn't exist)
print(word_break("bedbathandbeyo", ["bed", "bath", "bedbath", "bathand", "beyond"]))
# Test 5
# Correct result => ['314', '15926535897', '9323', '8462643383279']
print(
word_break(
"3141592653589793238462643383279",
["314", "49", "9001", "15926535897", "14", "9323", "8462643383279", "4", "793"],
)
)
# Test 6
# Correct result => ['i', 'like', 'like', 'i', 'mango', 'i', 'i', 'i']
print(
word_break(
"ilikelikeimangoiii",
[
"mobile",
"samsung",
"sam",
"sung",
"man",
"mango",
"icecream",
"and",
"go",
"i",
"like",
"ice",
"cream",
],
)
)
```
Elementary Algorithms — Introduces elementary algorithms and data structures. Includes side-by-side comparisons of purely functional realization and their imperative counterpart.
Open Data Structures — Provide a high-quality open content data structures textbook that is both mathematically rigorous and provides complete implementations. (Code)