Maximum sum of a Matrix where each value is from a unique row and column

0 0 6 minutes read

Given a matrix of size N X N, the task is to find maximum sum of this Matrix where each value picked is from a unique column for every row.
Examples:

Input: matrix = [[3, 4, 4, 4],
                 [1, 3, 4, 4], 
                 [3, 2, 3, 4], 
                 [4, 4, 4, 4]]
Output: 16
Explanation:
Selecting (0, 1) from row 1 = 4
Selecting (1, 2) from row 2 = 4
Selecting (2, 3) from row 3 = 4
Selecting (3, 0) from row 4 = 4
Therefore, max sum = 4 + 4 + 4 + 4 = 16
                        
Input: matrix = [[0, 1, 0, 1], 
                 [3, 0, 0, 2], 
                 [1, 0, 2, 0], 
                 [0, 2, 0, 0]]
Output: 8
Explanation: 
Selecting (0, 3) from row 1 = 1
Selecting (1, 0) from row 2 = 3
Selecting (2, 2) from row 3 = 2
Selecting (3, 1) from row 4 = 2
Therefore, max sum = 1 + 3 + 2 + 2 = 8

Approach:

Generate a numeric string of size N containing numbers from 1 to N
Find the permutation of this string (N!).
Now pairing is done between the permutations, such that each N! pairing has a unique column for every row.
Then calculate the sum of values for all the pairs.

Below is the implementation of the above approach:

C++

// C++ code for maximum sum of
// a Matrix where each value is
// from a unique row and column
 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
// Function to find the maximum sum in matrix
void MaxSum(int side, vector<vector<int> > matrix)
{
    string s;
    for (int i = 0; i < side; i++) {
        s += to_string(i);
    }
 
    // Permutations of s string
    vector<string> cases;
    do {
        cases.push_back(s);
    } while (next_permutation(s.begin(), s.end()));
 
    // List to store all sums
    vector<int> sum;
 
    // Iterate over all cases
    for (auto c : cases) {
        vector<int> p;
        int tot = 0;
        for (int i = 0; i < side; i++) {
            p.push_back(matrix[i] - '0']);
        }
        sort(p.begin(), p.end());
        for (int i = side - 1; i >= 0; i--) {
            tot += p[i];
        }
        sum.push_back(tot);
    }
 
    // Maximum of sum list is the max sum
    cout << *max_element(sum.begin(), sum.end()) << endl;
}
 
// Driver code
int main()
{
    int side = 4;
    vector<vector<int> > matrix = { { 3, 4, 4, 4 },
                                    { 1, 3, 4, 4 },
                                    { 3, 2, 3, 4 },
                                    { 4, 4, 4, 4 } };
    MaxSum(side, matrix);
 
    side = 3;
    matrix = { { 1, 2, 3 }, { 6, 5, 4 }, { 7, 9, 8 } };
    MaxSum(side, matrix);
 
    return 0;
}
// This code is contributed by rutikbhosale

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main 
{
 
  // Function to find the maximum sum in matrix
  public static void maxSum(int side, int[][] matrix) {
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < side; i++) {
      s.append(i);
    }
 
    // Permutations of s string
    List<String> cases = new ArrayList<>();
    permutation(s.toString(), cases);
 
    // List to store all sums
    List<Integer> sum = new ArrayList<>();
 
    // Iterate over all cases
    for (String c : cases) {
      List<Integer> p = new ArrayList<>();
      int tot = 0;
      for (int i = 0; i < side; i++) {
        p.add(matrix[i]);
      }
      Collections.sort(p);
      for (int i = side - 1; i >= 0; i--) {
        tot += p.get(i);
      }
      sum.add(tot);
    }
 
    // Maximum of sum list is the max sum
    System.out.println(Collections.max(sum));
  }
 
  // Function to generate all permutations of a string
  public static void permutation(String str, List<String> cases) {
    permutation("", str, cases);
  }
 
  private static void permutation(String prefix, String str, List<String> cases) {
    int n = str.length();
    if (n == 0) {
      cases.add(prefix);
    } else {
      for (int i = 0; i < n; i++) {
        permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1), cases);
      }
    }
  }
 
  // Driver code
  public static void main(String[] args) {
    int side = 4;
    int[][] matrix = { { 3, 4, 4, 4 }, { 1, 3, 4, 4 }, { 3, 2, 3, 4 }, { 4, 4, 4, 4 } };
    maxSum(side, matrix);
 
    side = 3;
    matrix = new int[][] { { 1, 2, 3 }, { 6, 5, 4 }, { 7, 9, 8 } };
    maxSum(side, matrix);
  }
}

Python3

# Python code for maximum sum of 
# a Matrix where each value is 
# from a unique row and column
 
# Permutations using library function
from itertools import permutations
 
# Function MaxSum to find
# maximum sum in matrix
def MaxSum(side, matrix):
         
    s = ''
    # Generating the string 
    for i in range(0, side):
        s = s + str(i) 
 
    # Permutations of s string
    permlist = permutations(s)
     
    # List all possible case
    cases = []
     
    # Append all possible case in cases list
    for perm in list(permlist):
        cases.append(''.join(perm))
     
    # List to store all Sums 
    sum = []
     
    # Iterate over all case
    for c in cases:
        p = []
        tot = 0
        for i in range(0, side):
            p.append(matrix[int(s[i])][int(c[i])])
        p.sort()
        for i in range(side-1, -1, -1):
            tot = tot + p[i]
        sum.append(tot)
     
 
    # Maximum of sum list is 
    # the max sum
    print(max(sum)) 
 
         
# Driver code 
if __name__ == '__main__': 
     
    side = 4
    matrix = [[3, 4, 4, 4], [1, 3, 4, 4], [3, 2, 3, 4], [4, 4, 4, 4]]
    MaxSum(side, matrix)
    side = 3
    matrix = [[1, 2, 3], [6, 5, 4], [7, 9, 8]]
    MaxSum(side, matrix)

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Gfg
{
  // Function to find the maximum sum in matrix
  public static void MaxSum(int side, List<List<int>> matrix)
  {
    string s = "";
    for (int i = 0; i < side; i++)
    {
      s += i.ToString();
    }
 
    // Permutations of s string
    List<string> cases = new List<string>();
    do
    {
      cases.Add(s);
    } while (NextPermutation(ref s));
 
    // List to store all sums
    List<int> sum = new List<int>();
 
    // Iterate over all cases
    foreach (var c in cases)
    {
      List<int> p = new List<int>();
      int tot = 0;
      for (int i = 0; i < side; i++)
      {
        p.Add(matrix[i][int.Parse(c[i].ToString())]);
      }
      p.Sort();
      for (int i = side - 1; i >= 0; i--)
      {
        tot += p[i];
      }
      sum.Add(tot);
    }
 
    // Maximum of sum list is the max sum
    Console.WriteLine(sum.Max());
  }
 
  // Helper function to generate permutations of a string
  private static bool NextPermutation(ref string s)
  {
    char[] a = s.ToCharArray();
    int n = a.Length;
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i < 0) return false;
    int j = n - 1;
    while (a[j] <= a[i]) j--;
    char temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    Array.Reverse(a, i + 1, n - i - 1);
    s = new string(a);
    return true;
  }
 
  // Driver code
  public static void Main()
  {
    int side = 4;
    List<List<int>> matrix = new List<List<int>> {
      new List<int> { 3, 4, 4, 4 },
      new List<int> { 1, 3, 4, 4 },
      new List<int> { 3, 2, 3, 4 },
      new List<int> { 4, 4, 4, 4 }
    };
    MaxSum(side, matrix);
 
    side = 3;
    matrix = new List<List<int>> {
      new List<int> { 1, 2, 3 },
      new List<int> { 6, 5, 4 },
      new List<int> { 7, 9, 8 }
    };
    MaxSum(side, matrix);
  }
}

Javascript

// JavaScript code for maximum sum of
// a Matrix where each value is
// from a unique row and column
 
// Function MaxSum to find
// maximum sum in matrix
function MaxSum(side, matrix) {
 
  let s = '';
  // Generating the string 
  for (let i = 0; i < side; i++) {
    s = s + i;
  }
 
  // Permutations of s string
  let permlist = permutation(s);
 
  // List all possible case
  let cases = [];
 
  // Append all possible case in cases list
  for (let i = 0; i < permlist.length; i++) {
    cases.push(permlist[i]);
  }
 
  // List to store all Sums 
  let sum = [];
 
  // Iterate over all case
  for (let i = 0; i < cases.length; i++) {
    let c = cases[i];
    let p = [];
    let tot = 0;
    for (let j = 0; j < side; j++) {
      p.push(matrix[s[j]]]);
    }
    p.sort();
    for (let j = side - 1; j >= 0; j--) {
      tot = tot + p[j];
    }
    sum.push(tot);
  }
 
  // Maximum of sum list is 
  // the max sum
  console.log(Math.max(...sum));
}
 
// Driver code 
function main() {
  let side = 4;
  let matrix = [
    [3, 4, 4, 4],
    [1, 3, 4, 4],
    [3, 2, 3, 4],
    [4, 4, 4, 4]
  ];
  MaxSum(side, matrix);
  side = 3;
  matrix = [
    [1, 2, 3],
    [6, 5, 4],
    [7, 9, 8]
  ];
  MaxSum(side, matrix);
}
 
// permutation function
function permutation(string) {
  if (string.length === 0) return [];
  if (string.length === 1) return [string];
  let result = [];
  for (let i = 0; i < string.length; i++) {
    let firstChar = string[i];
    let charsLeft = string.substring(0, i) + string.substring(i + 1);
    let innerPermutations = permutation(charsLeft);
    for (let j = 0; j < innerPermutations.length; j++) {
      result.push(firstChar + innerPermutations[j]);
    }
  }
  return result;
}
 
main();
// This code is contributed by Prince Kumar

Output:

16
18

Time complexity: O(K), where K = N!
Auxiliary Space complexity: O(K), where K = N!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!