@PraneethVT I think the time complexity would be, say numRows = k
, then there are A1 = 1 elements in 1st level,A2= 2 in 2nd level, A3 =3 in 3rd level ... Ak = k in k th level
. Then to sum them up, Sn = A1 + A2 + A3 +... + Ak = (1 + k) * k / 2
. Since there are Sn
numbers in total, and we need to visit every number once. Therefore, the time complexity is the number of elements in total, which is (1 + k) * k / 2
. In general, we could say it's O(k^2)
.
@wxl163530
Life Sucks, Suck It Harder
Posts made by wxl163530

RE: My concise solution in Java

RE: Using HashMap,BFS Java Solution
@Jerry Would it be better to use hashmap? Since if we use treemap, the search, insert, delete time complexity would be logk where k is the size of tree, k is roughly the breath of the tree.Therefore, we visit very node once, the worst time complexity would be
O(n*logk)
. But if we use hashmap, we could search and add nodes withinO(1)
time complexity. 
RE: Easiest 9ms Java Solution
One thing confuses me is how does your solution skip duplicate result. For instance,
((())
is the given input, would your solution include duplicated outputs by deleting 1st 2nd or 3rd(
respectively? Then in this case, the output would have 3(())

RE: Accepted 16ms c++ solution use backtracking, easy understand.
@younghobbits You're right, it could not be T(n) = T(n1) + T(n2) + T(n2) ... since the same number could be used unlimited times.

RE: *Java* an easytounderstand divide and conquer method
The time complexity should be
O((MN)log4(3))
just as what @StefanPochmann points out. The recursive equation of this solution isT(n) = 3T(n/4) + O(1)
Then according to master method, any equation in form ofT(n) = aT(n/b) + f(n)
could fall into 3 case if it is solvable by master method. AndT(n) = 3T(n/4) + O(1)
matches exactly the1st
case, which isT(n)=Θ(n^logb(a))
. For more details, refer to Master Method or The Book  CLRS 
RE: What is the objective of this question
@wxl163530 Today is 1/15/2018, and now its my second time to deal with this question. I made the same mistake as treating the buff in read4() as the source file😲