Leetcode Problem 800-899
O(N^2) Time and O(1) Space
- Use inbuilt reverse() function to reverse the vector.
- To Toggle we can use either
y=1-y
or y^=1
Using stack
- We use stack to store the score of each parentheses.
- If we meet a
(
, we push 0 to the stack.
- If we meet a
)
, pop call 0βs and multiple the result with 2, also if there is only one () then result will become 0 so store val as max(1, 2*val)
, push the result to the stack.
- calculate total result from stack.
- TC: O(N)
- SC: O(N)
Leetcode Approach 3: Count Cores
Intuition
- The final sum will be a sum of powers of 2, as every core (a substring (), with score 1) will have itβs score multiplied by 2 for each exterior set of parentheses that contains that core.
Algorithm
- Keep track of the balance of the string, as defined in Approach #1. For every ) that immediately follows a (, the answer is 1 « balance, as balance is the number of exterior set of parentheses that contains this core.
kkzengβs explanation:
The key idea is that:
- the balance tells you what βdepthβ you are at since with each β(β we are increasing the depth by 1 (kind of similar to the concept in Solution 2).
- the βcoresβ () are the only structure that provides value, the outer parentheses just add some multiplier to the cores. So we only need to be concerned with those.
With those 2 ideas in mind, we are able to calculate how much the βcoreβ is worth directly without having to calculate substructures recursively and then apply multipliers.
E.g. For the example of ( ( ) ( ( ) ) )
, with the stack method, we are calculating the inner structure ( ) ( ( ) )
first and then multiplying the score by 2. With the 3rd method, by knowing the depth of the core, we are actually performing this calculation ( ( ) )
+ ( ( ( ) ) )
.
O(N*M) Time and O(N*M) space
- Get no of rows and columns of given matrix.
- Create a new matrix of with no.rows=no.columns and no.columns=no.rows.
- Iterate over the matrix and copy the values from the given matrix to the new matrix
ans[j][i]=matrix[i][j]
;
- Space can be optimizes in case of square matrix, where we can use in place swapping of rows and columns.
Brute force (TLE)
- For every
k
from 1 to max(piles)
, We check if hour spent is h
or less.
- If it is then we return that
k
.
- TC: O(n^2)
- SC: O(1)
Binary Search (AC)
- We can observe that we are checking for every
k
from 1
to max(piles)
, we can optimize this algorithm by using binary search.
- Here the main observation for binary search is, if we can finish eating all bananas in
i
hours, then we can finish eating all bananas in i+1
hours.
- We need to minimize the result so we check for lesser i if the answer for current i is possible.
- TC: O(N*logM)
- SC: O(1)
O(N) Time solution
- We can traverse through the whole linked list and count the number of node.
- Then we travel from start until we reach to the middle.
- Then return temp, which is the middle node.
O(N) Slow and Fast pointer
- NOTE: It works for all
Find middle
Questions.
- Each time, slow go 1 steps while fast go 2 steps.
- When fast arrives at the end, slow will arrive right in the middle.
fast != NULL
for odd number of nodes.
fast->next != NULL
for even number of nodes.
Greedy Two pointer
- Code is self explanatory.
- TC: O(N log N)
- SC: O(1)