Leetcode Problem 300-399
Brute force (TLE)
- Directly calculate the sum of area.
Row Prefix sum (AC)
- We know the concept of prefix sum for 1D array, we can apply it to 2D array.
- Calculate prefix sum of each row.
- From the calculated prefix sum for row, Take only part which is in the area and add it to the answer.
- Return the answer.
Area Prefix sum (AC)
- Leetcode official solution has very good explanation for this approach.
Recursive Solution (TLE)
- For ith day we can
doNothing or buyOrSell.
doNothing is simple we just move to next day with current states.- For
buyOrSell:
- if we can buy then we can choose from
doNothing or sell
- To buy, we have to subtract the price from the current balance and move to next day where we cannot buy again.
- if we can sell then we can choose from
doNothing or buy
- To sell, we have to add the price to the current balance and rest 1 day(cooldown).
- then for
i+2nd day we can again buy.
- We choose the max of
doNothing and buyOrSell
- TC: O(2^N)
- SC: O(N)
Memoization (AC)
- We can easily convert recursive code to memoized code with 2-3 extra lines.
- Fill dp array with -1.
- If we already calculated the value for i, then return it.
- else calculate and store new value.
- TC: O(N), O(N*2)–>O(N)
- SC: O(N), O(N*2)–>O(N)
Tabulation (AC)
- For iteration direction and order, remember with bottom-up we start at the base cases.
- Therefore we will start iterating from the end of the input.
- TC: O(N)
- SC: O(N)
Space optimized dp
- For any day, we just need the answers for the next 2 days i.e day + 1 and day + 2.
- which means that we need to store the answers of 3 states (day, day + 1, day + 2).
- That’s why we have taken an Array of [3][2] always and did modulo by 3.
- TC: O(N)
- SC: O(1)
NOTE: This question is same as 1081
Solution
- We store the frequency of characters in a hashmap or vector.
- Create an answer string to store the result.
- for every character in the string.
- Decrement the frequency of the character.
- If its already visited the continue.
- else remove all characters from ans string that are greater than current character.
- Add current character in the answer string.
- mark visited as true.
- Return the answer string.
- TC: O(N)
- SC: O(26)=O(1)
Recursive solution (TLE)
- For a coin we have 2 choices:
- if last coin have value less than or equal to amount,we have choice to use or not use it, We return the minimum of the two.
- else we don’t have a choice and we cannot use it, we return not-use.
- If we use the coin we will increase the count by 1 and subtract the value of the coin from the amount.
- The base condition arises when the amount is 0, that means we found the answer, return 0
- and if index goes beyond the limits of the array, that means we cannot use the coin and we return INT_MAX-1.
Memoization (Top-Down) (AC)
- The simple recursively solution is not efficient nd results in TLE, because its doing so many calls again and again.
- We
rest of the code is same, we just need to store new calculated values in the table, if the value is already present then we can return value itself.
- TC: O(N*amount)
- SC: O(N*amount)
Tabulation (Bottom-Up) (AC)
- The memoization solution is acceptable but we can get rid of recursive calls with iterative dp.
- TC: O(N*amount)
- SC: O(N*amount)
DFS with memoization
STL
DP
- Even numbers have same set bits as n/2.
- Odd numbers have set bits prev+1.
General Solution for any power
- num should be greater than 0.
- Divide n by 4 until its possible to divide by 4.
- if n is 1 return true else false.
Bitwise Solution
- Power of 4, numbers have those 3 common features.
- greater than 0.
- Second,only have one ‘1’ bit in their binary notation,so we use x&(x-1) to delete the lowest ‘1’,and if then it becomes 0,it prove that there is only one ‘1’ bit.
- the only ‘1’ bit should be locate at the odd location,for example,16.It’s binary is 00010000.So we can use ‘0x55555555’ to check if the ‘1’ bit is in the right place.With this thought we can code it out easily!(0x55555555 is the hex representation of ‘1010101010101010101010101010101’)
O(N) time and O(1) space, using stack
- Using stack we can reverse the string.
O(N) Time , recursive
- if i is the middle then we can stop (it’s base condition)
- else we swap ith and n-i-1th element
- we recur for next position of i, i.e i+1.
O(N) Time two pointer solution
- swap start and end pointers.
O(N*M) Time and O(N) Space
- Brute force
- for every element in nums1, check if it exists in nums2
- if it exists then add it to the ans and set it to -1 and break inner loop, so duplicate will not be included.
- return ans
same as is_subsequence problem.
O(N) Time O(N)=O(26) constant space
- calculate frequency of each letter in magazine
- iterate over ransomNote and decrement frequency of each letter
- if any letter frequency is less than 0, return false
O(N^2) Time and O(1) space
- Brute force
- For every character check if it appears in the string more than once
O(N) Time and O(N)=O(26) constant space
- Store frequency of every character in a hash table
- Iterate through the hash table and check if the character is Unique
Brute force
- Traverse every char in s and check if it is present in t or not.
- if not present, return the char.
- TC: O(n^2)
- SC: O(1)
sorting
- Sort s and t.
- traverse s and t and check if they are equal or not.
- if not equal, return the char.
- TC: O(nlogn)
- SC: O(1), excluding the sorting space.
Hashing
- We can use hashmap to store the frequency of characters.
- first traverse
s and increase frequency and then traverse t and decrease frequency.
- Now traverse map anf if
it.second<0 return it.first.
- TC: O(n)
- SC: O(n)
Bit Manipulation
- We can use bit manipulation to solve this problem.
- We can use XOR to find the difference.
- TC: O(n)
- SC: O(1)
Exhaustive Search
- if size of s is greater than t, then its obvious that s is not a subsequence of t.
- We will try to find s in t.
- traverse through s and find every character in t.
- if at the end out pointer reaches the end of s, then s is a subsequence of t, else not.
- TC: O(n), where n is the length of t. Each step we either increment the pointer on s or the pointer on t.
Recursive solution
- base case:
- if s is empty, s is a subsequence of t, return true
- if t is empty, subsequence of t not found, return false
- check if first character of s matches with first character of t
- if yes, then check for strings starting from next character
- if no, then check for strings starting from next character of t with same s
- NOTE: substr(ind, size) function creates new string from string starting from given index to given size(default till end).
Dynamic Programming
- We can use dynamic programming to solve this problem.(specifically map and binary search)
- We will store the index of every character in t in a map with key as character and value as vector of indices.
- Now we will iterate over s and for every character in s, we will find the index of that character in t.
- we should find index greater than the previous index, previous index can be stored in a variable.
- in between we can not find any character of s in map then return false.
- also if we reach the end of t and still some characters are left in s, then return false.
- else return true.
- TC: O(nlogn), where n is the length of t. Each step we either increment the pointer on s or the pointer on t.
- NOTE: This is best solution if there are many s and we want to check them in same t.(follow up of this problem)
- Ex. s = ‘abcd’, t = ‘abcdabcdabcd’
- map = {a: {0, 4, 8}, b: {1, 5, 9}, c: {2, 6, 10}, d: {3, 7, 11}}