Click here to see the full article post
In the DP explanation , do you mean shifting towards "left" rather than shifting towards "right" ?
@irajdeep It means that we are counting from the rightmost end OR we are shifting by the given amount towards the left.
@travellinglina you are right. Corrected. Thanks.
In approach #2, if we have one number which means n = 1, if k = 1, then the answer is 1, if we check for k == 0 first, then the answer is 2.
I think maybe we need to check if k == 0 and return 1 first rather than checking the value of n first.
@Todoloki for n=1 and k=1 answer is 0. And if we check k first then for n=0 and k=0 answer will be 1 but it should be 0.
@vinod23 Thank you. I realized where I am wrong. For n = 1, k can be in range [1, 1000], so we can not check the value of k first since invalid cases might exist and we need to deal with them properly.
Really awesome article!
I guess there is a problem in the figure or maybe I just dont understand it!
The question is when n = 5 and k=1, you put 15243, 15324, 25134 (they are not 1 inverse I guess )
Looking forward to your reply
15243, 15324, 25134 all have four inversions. Here we are placing 5 in an array of n-1 and k=1. I have updated the image. Please have a look. Thanks.
if answer of this que can be 1000000007 this much large how return type int is possible ...???
@dreamiit 1000000007 lies in the integer range [-2,147,483,648 to 2,147,483,647].
Really nice article. One learns a lot when going through the solution in a step by step manner, starting with greedy and then optimizing it step by step!
In approach 5, I think accumulate sum means dp[i][j]=count(i,j) + dp[i][j-1], did I get it wrong?
@LeonCheng It Should be dp[i][j]=count(i,j)+cum_sum, where cum_sum will be dp[i-1][j]-dp[i-1][j-i].
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.