K_Inverse_Pairs_Array.java

package AllCodes;

public class K_Inverse_Pairs_Array {
	//Optimize Solution
	 public int kInversePairss(int n, int k) {
	        if (k > n * (n - 1) / 2) // n numbers can generate at most n * (n - 1) / 2 inverse pairs
	            return 0;
	        
	        if (k == n * (n - 1) / 2 || k == 0)
	            return 1;
	        
	        int mod = 1000000007;
	        int[][] dp = new int[n + 1][k + 1];
	        
	        for (int i = 1; i < n + 1; i++) {
	            dp[i][0] = 1; // deal with j = 0
	            for (int j = 1; j < Math.min(k, i * (i - 1) / 2) + 1; j++) {
	                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - (j >= i ? dp[i - 1][j - i] : 0)) % mod;
	                // all dp[i][j] modulo 10^9 + 7
	                // so dp[i - 1][j - 1] might bigger than dp[i][j - 1] + dp[i - 1][j]
	                if (dp[i][j] < 0) 
	                    dp[i][j] += mod;
	            }
	        }
	        
	        return dp[n][k];
	    }
	
	
	//Better Solution
	public int kInversePairs(int n, int k) {
        int[][]dp = new int[n+1][k+1];
       int mod=1000000007;
       for(int i = 1; i <= n; i++){
           for(int j = 0; j <= k; j++){
               if(j == 0) 
                   dp[i][j] = 1;    
               else{
                   for(int p = 0; p <= Math.min(j,i-1); p++)
                       dp[i][j] = (dp[i][j] + dp[i-1][j-p]) %mod ;
               }
           }
       }
       return dp[n][k];
   }
}