is the time complexity 3^N and space complexity 3^N???
TarzanNJane
@TarzanNJane
Posts made by TarzanNJane

is the time complexity 3^N and space complexity 3^N???

RE: [recommend for beginners]clean C++ implementation with detailed explanation
is the time complexity 3^N and space complexity 3^N???

could not figure out what's wrong with my c++ BIT solution HELP
I thought about my solution for a very long time, couldn't figure out what's wrong. It bothers me a lot. Any insight is appreciated!!
More Details
Errors:
Input:
[2,5,1]
2
2
Output:
197
Expected:
3The same idea as 315 Count of smaller numbers after self.

get the all sums from[0,i] as sum[i]

sort sum vector as clone vector, and reindex elements in sum according to its index in clone vector. Put sum element value as map reflect's key, new index as reflect's value.
3.add vector sum element from back to front, and at the same time find valid elements index range [idx1,idx2] in clone which satisfies the lowerbound and upperbound condition. 
get the sum from node 0 to node idx1 and sum from node 0 to node idx2 in our BIT. If the node is inserted into the BIT already we will find the node in our BIT. So we can know the node amount in BIT which satisfies our bound condition.
class Solution { public: vector<long>tree,clone; int countRangeSum(vector<int>& nums, int lower, int upper) { int n=nums.size(); vector<long>sum(n+1); for(int i=1;i<=n;i++) sum[i]=sum[i1]+nums[i1];// step1 clone=sum; sort(clone.begin(),clone.end()); tree.resize(sum.size()+1); unordered_map<long,int>reflect; for(int i=0;i<clone.size();i++) reflect[clone[i]]=i;//step2
int res=0; for(int i=sum.size()1;i>=0;i) { int idx1=binarysearch(sum[i]+lower,true); int idx2=binarysearch(sum[i]+upper,false); res=res+count(idx2)count(idx1); add(reflect[sum[i]]); //step3 } return res; } int binarysearch(long val, bool includeself) { if(includeself) return lower_bound(clone.begin(),clone.end(),val)clone.begin(); return upper_bound(clone.begin(),clone.end(),val)clone.begin();
}
void add(int pos){ pos=pos+1; while(pos<tree.size()) { tree[pos]++; pos=pos+(pos&pos); } } int count(int pos){ int cnt=0; pos=pos+1; while(pos>0) { cnt=cnt+tree[pos]; pos=pos(pos&pos); } return cnt; }
};


RE: Java DFS + boundary cell turning solution, simple and clean code, commented.
@aritra90tnp because you don't need to visit the four boundary columns and rows again
you started dfs from them 
RE: I believe undirected graph neighbor list should always contain each other
i have the same question. It's more like a directed graph

RE: [C++] O(n*amount) time O(amount) space DP solution
Great solution! but if I change vector<int> A(amount+1, amount+1); to vector<int> A(amount+1, INT_MAX);
and change the final judge to return A[amount] ==INT_MAX ? 1 : A[amount];
It couldn't pass. That is interesting and I am curious to know why........ 
RE: Concise C++ without storing all values at initialization
HI, thanks for your great solution! Just want to ask you why you can use
int size = nestedList.size();
nestedList is NestedInteger class, and in the definition it doesn't mention a size() method ... 
RE: Why does a greedy solution work for this problem?
Hi, could you explain a little more why:
X1 <= M1 (otherwise M1 is not covered)X2 <= M2 (otherwise M2 is not covered)
.
.
.
Xk' <= Mk' (otherwise Mk' is not covered)??
Thanks a lot:) 
RE: Does anyone know why second DFS(12 ms) is slower than first DFS(8ms) solution?
because there may be many nodes before tmp reaches the right end