🌟 Today's Challenge 🌟
2976. Minimum Cost to Convert String I
❔ Problem: Given 2 strings source and target and two arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i], The task is to find the minimum cost to change the source string to target.
➡️ It is pretty much the same as yesterday's one, right? so I did the same thing and got TLE....cuz I was calling the dijkstras function for every character in source...which is inefficient because of the repetitive work. so we need to store the results of transformations to avoid redendant computation...the other thing is the same.
📊 Time Complexity: O(n^2 * log(n))
📂 Space Complexity: O(n^2)
https://leetcode.com/problems/minimum-cost-to-convert-string-i/
#LeetCode #DailyChallenge #DijkstrasAlgorithm #Heap #Hashmap
🌟 Today's Challenge 🌟
238. Product of Array Except Self
❔ Problem: Given an array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]...but without using division operator and with linear time complexity
➡️ this means...for every element, we need the product of elements before it and after it...where prefixsum(in this case prefix product) comes in to play....I did the prefix product in one iteration. And in other iteration, I did suffix product while also multiplying it with its corresponding prefix product
📊 Time Complexity: O(n)
📂 Space Complexity: O(n)
https://leetcode.com/problems/product-of-array-except-self/description/
#LeetCode #DailyChallenge #PrefixProduct
2976. Minimum Cost to Convert String I
❔ Problem: Given 2 strings source and target and two arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i], The task is to find the minimum cost to change the source string to target.
➡️ It is pretty much the same as yesterday's one, right? so I did the same thing and got TLE....cuz I was calling the dijkstras function for every character in source...which is inefficient because of the repetitive work. so we need to store the results of transformations to avoid redendant computation...the other thing is the same.
📊 Time Complexity: O(n^2 * log(n))
📂 Space Complexity: O(n^2)
https://leetcode.com/problems/minimum-cost-to-convert-string-i/
#LeetCode #DailyChallenge #DijkstrasAlgorithm #Heap #Hashmap
🌟 Today's Challenge 🌟
238. Product of Array Except Self
❔ Problem: Given an array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]...but without using division operator and with linear time complexity
➡️ this means...for every element, we need the product of elements before it and after it...where prefixsum(in this case prefix product) comes in to play....I did the prefix product in one iteration. And in other iteration, I did suffix product while also multiplying it with its corresponding prefix product
📊 Time Complexity: O(n)
📂 Space Complexity: O(n)
https://leetcode.com/problems/product-of-array-except-self/description/
#LeetCode #DailyChallenge #PrefixProduct