Leetcode Problem 200-299
O(N) Time and O(1) Space
O(N) Time and O(1) Space, recursive
- if head is null return null.
- if value of current node is val we not include it else we include it.
O(N) Time and O(1) space, iterative
- Initialize three pointers prev as NULL, curr as head and next as NULL.
- Iterate through the linked list. In loop, do following.
- Before changing next of current, store next node
next = curr->next
- Now change next of current This is where actual reversing happens
curr->next = prev
- Move prev and curr one step forward
prev = curr
curr = next
O(N) Time and O(1) space, recursive
- Divide the list in two parts - first node and
rest of the linked list.
- Call reverse for the rest of the linked list.
- Link rest to first.
- Fix head pointer
Topological Sort + DFS
- Make adjacecncy list
- Detect CYCLE…If present then return empty array
- Find toposort and store it in stack
- Apply DFS and find topological sort
READ
-
| [✅ [C++/Python] Simple Solutions w/ Explanation |
Topological Sort using BFS & DFS](https://leetcode.com/problems/course-schedule-ii/discuss/1642354/C%2B%2BPython-Simple-Solutions-w-Explanation-or-Topological-Sort-using-BFS-and-DFS) |
Backtracking Solution
- For this problem as we have to try all the numbers to check if they can form the sum or not, we can use backtracking.
- Create a helper function which takes the size of the combination, the sum, the answer vector, the temporary vector and the starting number.
- If the sum is 0 and the size of the temporary vector is equal to the size of the combination, we found the combination, so we push it to the answer vector and return.
- If the sum is less than 0 or the size of the temporary vector is greater than the size of the combination, we can’t form the sum, so we return.
- Now we try all the numbers from the starting number to 9.
- We push the number to the temporary vector and call the helper function with the sum - number, as we have used the number.
- After the recursive call we pop the number from the temporary vector.
- TC:O(2^n)
- SC:O(k)
O(N^2) Time and constant space
- Check for every element, if it is present in the array using 2 loops.
O(N log N) Time and constant space
- We can sort the array, so duplicate elements will be next to each other.
O(N) Time and O(N) Space
- We can use a hash table to store the elements.
Sliding window + hashmap
- We know that if there exist any duplicate then it should be in range
abs(i-j) <= k.
- So we can create map to store the index of the element.
- when we encounter the duplicate we can check if the index is in range
abs(i-j) <= k.
- If it does
return true else give the index of the number to the map.
- Finally
return false if there is no duplicate in the range.
- TC: O(N)
- SC: O(N)
Sliding window + set
- instead of map we can use set to store the elements.
- Here we can reduce space complexity to
O(k).
- TC: O(N)
- SC: O(k)
Dynamic Programming
- 1 square itself can create a square.
- Also We can observe that if there are 1 in cell above, cell left and cell diagonally then we can create a new 2x2 square.
- So the relation can be found as
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- Also we maintain a max_sq to get the maximum ans.
- finally we return max_sq ** 2
- TC: O(nm),n=row , m=col
- SC: O(nm)
READ
O(N) Time
- we Can traverse the whole tree and count the number of nodes.
O(log N * log N) Time
- The idea behind the algorithm is - A complete binary tree has
2^h - 1 nodes, where h is the height of the tree.
- so we get the left and right hight of the tree.
- if the are equal, then we can directly return
2^(left) - 1
- else we check for its right and left subtree and return
1 + countNodes(root->left) + countNodes(root->right);
O(N) Time recursive solution
- if root is null return null
- we just need to swap the left and right children of each node recursively.we can use inbuilt swap function or implement our own swap function.
- We can travel in preorder as well as postorder , both solutions are accepted.(here is preorder solution)
O(N) Time O(N) stack iterative solution
- We use stack instead of recursive stack.
Using Stack
- Scan the string from left to right
- If the current character is a digit add it to the number currentNumber.
- Otherwise, the current character must be an operation (+,-,*, /). Evaluate the expression based on the type of operation.
- Addition (+) or Subtraction (-): We must evaluate the expression later based on the next operation. So, we must store the currentNumber to be used later. Let’s push the currentNumber in the Stack.
- Multiplication (*) or Division (/): Pop the top values from the stack and evaluate the current expression. Push the evaluated value back to the stack.
- Once the string is scanned, pop from the stack and add to the result.
- TC: O(n)
- SC: O(n)
Without Stack
The approach works similar to Approach 1 with the following differences :
- Instead of using a stack, we use a variable lastNumber to track the value of the last evaluated expression.
- If the operation is Addition (+) or Subtraction (-), add the lastNumber to the result instead of pushing it to the stack. The currentNumber would be updated to lastNumber for the next iteration.
- If the operation is Multiplication (*) or Division (/), we must evaluate the expression lastNumber * currentNumber and update the lastNumber with the result of the expression. This would be added to the result after the entire string is scanned.
- TC: O(n)
- SC: O(1)
Intuitive Solution
- We traverse the array and find right element to add.
- If we found then change flag to true.
- else add arrow and right element to the array as string and store new left element i.e. nums[i] and flag = true.
- TC: O(n)
- SC: O(1)
Intuitive Solution
- We traverse the array and find right element to add.
- If we found then change flag to true.
- else add arrow and right element to the array as string and store new left element i.e. nums[i] and flag = true.
- TC: O(n)
- SC: O(1)
Brute force
- We check for all the elements, if it appears more than n/3 times, we add it to the result vector.
- TC: O(N^2)
- SC:O(1)
O(N) Time and O(1) space
- we Can take a vector or unordered_map to store the frequency of each element.
- We traverse the hash map/ vector to find the n/3 frequency.
- if we found we return the element.
- TC: O(N)
- SC:O(N)/O(N^2) - Yes if we use unordered_map it’s worst case time complexity is O(N^2), which occurs when all elements are divisible by prime number and result in collision. But if we use frequency vector it’s worst case time complexity is O(N).
Moore’s Voting Algorithm
- TC:O(N)
- SC:O(1)
- The intuition and method is same as
majority element problem but here we maintain 2 cnt variables and 2 candidate because in the question it is given that at most 2 majority element will be present or there may be no element present.
Inorder traversal
- Binary search tree in inorder traversal gives sorted values.
- So we can find kth smallest from the list.
- TC: O(N)
- SC: O(N), To store inorder traversal.
Get kth while traversing.
- We don’t need to traverse whole tree, instead we can just traverse until we find kth smallest element.
- TC: O(N)
- SC: O(N)
Above method in iterative way.
O(1) AMORTIZED Time solution
- AMORTIZED: Most of the times operations are O(1) time. Sometimes it will be O(n) time. But total time for all the operations will be O(1).
- Using 2 stacks; one is used for read and another for write.
Brute force
- Store the element of the linked list in the array or string and check if the array is palindrome.
- TC: O(N)
- SC: O(N)
Optimized
- Use two pointers to traverse the linked list.
- We find the middle of linked list and reverse the second half of the linked list.
- Then we compare the first half and the second half of the linked list.
- if the second half of the linked list reaches to null return true. Otherwise return false.
- TC: O(N)
- SC: O(1)
O(N) Time recursive solution
- we traverse the tree and find p and q;
- if one of child node is null return another
- else both are not null return the root(curr node), that means left and right are p and q.
- Reference: link for recursive solution.
O(N) Time iterative solution
O(N) Time and O(N) Space
- Find the path from the root node to node n1 and store it in a vector or array.
- Find the path from the root node to node n2 and store it in another vector or array.
- Traverse both paths until the values in arrays are same. Return the common element just before the mismatch.
O(N) Time recursive solution
- we traverse the tree and find p and q;
- if one of child node is null return another
- else both are not null return the root(curr node), that means left and right are p and q.
- Reference: link for recursive solution.
Dumb Question 😂🤣🤣
- Agree😂, not able to think this.
- We just need to copy the next node’s value to the current node and then delete the next node.
MUST READ:
let’s analyze why this problem **isn’t a good interview question.**
The whole point of asking any candidates a linked list problem is to test if the candidates think about edge cases, including:
1. Dereferencing Null Pointer, usually targeting tail pointer
2. When given Head is None
3. When there are duplications in the list
This question specifically mentioned all the above edge cases and extracted them out for you Someone who can solve this problem might not even think of all the edge cases, which can backfire on them in real interview settings
Intuitive Solution
- We can take the product of all the elements in the array and then divide it by the element at the current index.
- We should take care of cases where num == 0.
- If there are more than 1 zero ans array will be all 0.
- If there is only one 0 then ans array will be all 0 except at the index where 0 appears.
- TC: O(N)
- SC: O(1)
- Since we need product of left and right elements, we can think of following solution
- We precalculate the product form left side in the left array and the product from right side in the right array.
- Here corner cases are:
- ans[0] = right[1]
- ans[n-1] = left[n-2]
- TC: O(N)
- SC: O(N), since we are using 2 extra vectors to store the prefix product and suffix product.
Space optimization
- Instead of using 2 extra left and right array for storing prefix and suffix product, we can use owr ans vector to do both.since its given that ans vector will not considered as extra space.
- first store the prefix multiplication in ans vector.
- Then we ge ans[i] by multiplying
ans[i-1] and right[i+1] here right[i+1]=prod so ans[i] = ans[i - 1] * prod;
- from right each time we get num from right side and multiply it with the previous product.
- finally
ans[0]=prod itself
- TC: O(N)
- SC: O(1)
Read
O(N logN) Time and constant space
- Sort both strings and compare them.
- if they are equal, return true else false.
O(N) Time and O(N)=O(26) constant space
- We store frequency of each character in a hash table.
- Decrement the frequency of each character in hash table which is in the t.
- If any frequency is not zero, return false.
Only 2 loops
- First confirm sizes of both strings is same.
- We can avoid 3rd loop by checking if the frequency of each character less than 0 then return false.
- return true by default.
Brute Force
Mathematical solution
O(N^2) Time
O(NlogN) Time Sorting solution
- Since we have condition that
exactly two elements appear only once and all the other elements appear exactly twice.
- First we sort the nums array.
- if we found duplicates we increase i by 2 else we add number in ans.
- if ans.size()==2 thn we can break loop, since we have only 2 unique elements.
O(N) Time HashMap solution
- We can use
set or map to solve this problem in O(N) time.
O(N) Time O(1) Bit Manipulation solution
Idea is to use property of XOR:
1. xor(a, a) = 0
2. xor(a, 0) = xor(0, a) = a
3. xor(1, 1) = xor(0, 0) = 0
4. xor(1, 0) = xor(0, 1) = 1
5. xor(a, b) = c => xor(a, c) = b and xor(b, c) = a
Let two distinct elements be: first and sec. Now, firstXorSec := xor(first, sec) = xor(nums[i], 0), 0 <= i < [n:= nums.size()], why? because nums has odd and even freq. elements, doing xor will cancel out elements with even freq. using the 1. property of xor. So, at the end, xor of only odd freq. elements i.e first and sec remains.
Now, first != sec => there is at least 1 set bit in firstXorSec. Using 4. property of xor, one of first and sec, must have a set bit (Let it be first). We find/ denote this rightmost set bit using mask: has all bits 0 except the rightmost set bit in firstXorSec. So, we can divide the elements in nums in two groups A and B, where:
1. groupA: (num & mask) == 1 i.e bit is set
2. groupB: (num & mask) == 0 i.e bit is not set
Clearly, both first and sec belong to different groups and since, all other elements occurs in pair, so, we can safely again use 1. property of xor to generate first. Finally, using 5. property of xor, we have sec = xor(firstXorSec, first)
O(NlogN) by Sorting
- With sorting we can get missing number.
O(N) Time
- Calculate the sum of all elements in the array.
- Subtract the sum of all elements in the array from the sum of all elements in the range 1 to n.
O(log N) Time solution
- Slight modification of binary search.
- l=1,r=n;
O(N) Time solution
- We will shift all non zero elements at front
- Then remaining elements will be filled with zeros
O(N) Time snowball solution
- The idea is that we go through the array and gather all zeros on our road.
- If element is 0, increase size of snowball by 1.
- else we swap it with (i-snowball)th element.
- NOTE: here we used temp variable instead of direct swapping for avoiding unnecessary swapping. For ex.
[1] no swap required.
O(N^2) Brute force
- check for all numbers if duplicate number exists.
O(NlogN) Sorting
- Sort the array and duplicate numbers will be next to each other.
O(N) Time O(N) space, Hash Table
- With the help of hash (set/map/vector) we can find the duplicate number.
O(N) Time O(1) space, Floyd’s Cycle Detection Algorithm
Hashmap Solution
- Maintain 2 hash maps, one mapping pattern to string and another mapping string to pattern.
- Using c++ stringstream we can easily get each word in string on the fly.
- Initialize a variable say
i with 0 to count words in given string.
- We traverse the stringstream and check if the word is in the hashmap.
- If it is not in the hashmap1,
- check if the word is in hashmap2,i.e if its mapped already with other character or not.
- If it is then map the word with character in the pattern and map character in the patter with the word. Increase the i.
- else return
false.
- else the word in the hashmap1
- Check if the word is mapped with the same character or not.
- Increment the i, i.e.words count.
- Finally return of
i==pattern.size(), i.e. count of words in string and pattern same or not.
- TC: O(N)
- SC: O(N), O(N)+O(N) 2 hashmaps.
Counting Solution
- We can simply count the number of bulls and cows.
- Take count vector to store the count of each digit in secret.
- Traverse the secret and guess string and if the digit is same we increment the bulls.
- If the digit is not same we increment the count of that digit in secret and decrement the count of that digit in guess.while incrementing the cows both time.
- Finally we return the bulls and cows is required format.
- TC: O(N)
- SC: O(1), since the count vector is of constant size.