Data Modelling & AI Data Structure & Algorithm

Divide Matrix into K groups of adjacent cells having minimum difference between maximum and minimum sized groups

By Umr Jansen

23 June 2025

0

2

Given N rows and M columns of a matrix, the task is to fill the matrix cells using first K integers such that:

Each group of cells is denoted by a single integer.
The difference between the group containing the maximum and the minimum number of cells should be minimum.
All the cells of the same group should be contiguous i.e., for any group, two adjacent cells should follow the rule |x_i+1– x_i| + |y_i+1 – y_i| = 1.

Examples:

Input: N = 5, M = 5, K = 6
Output:
1 1 1 1 1
3 2 2 2 2
3 3 3 4 4
5 5 5 4 4
5 6 6 6 6
Explanation:
The above matrix follows all the conditions above and dividing the matrix into K different groups.

Input: N = 2, M = 3, K = 3
Output:
1 1 2
3 3 2
Explanation:
For making three group of the matrix each should have the group of size two.
So, to reduce the difference between the group containing maximum and minimum no of cells and all the matrix cells are used to make the K different groups having all the adjacent elements of the same group follow the |x_{i + 1} – x_i| + |y_{i + 1} – y_i| = 1 as well.

Approach: Below are the steps:

Create the matrix of size N * M.
To reduce the difference between group containing max and min no of cells, fill all the part with at least (N*M)/ K cells.
The remaining part will contain (N * M)/ K + 1 no of cells.
To follow the given rules, traverse the matrix and fill the matrix with the different parts accordingly.
Print the matrix after the above steps.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to fill the matrix with
// the given conditions
void fillMatrix(int** mat, int& row,
                int& col, int sizeOfpart,
                int noOfPart, int& start,
                int m, int& flag)
{
 
    // Count of parts with size sizeOfPart
    for (int i = 0; i < noOfPart; ++i) {
 
        int count = 0;
 
        while (count < sizeOfpart) {
 
            // Assigning the cell
            // with no of groups
            mat[row][col] = start;
 
            // Update row
            if (col == m - 1
                && flag == 1) {
                row++;
                col = m;
                flag = 0;
            }
            else if (col == 0
                     && flag == 0) {
                row++;
                col = -1;
                flag = 1;
            }
 
            // Update col
            if (flag == 1) {
                col++;
            }
            else {
                col--;
            }
 
            // Increment count
            count++;
        }
 
        // For new group increment start
        start++;
    }
}
 
// Function to return the reference of
// the matrix to be filled
int** findMatrix(int N, int M, int k)
{
 
    // Create matrix of size N*M
    int** mat = (int**)malloc(
        N * sizeof(int*));
 
    for (int i = 0; i < N; ++i) {
        mat[i] = (int*)malloc(
            M * sizeof(int));
    }
 
    // Starting index of the matrix
    int row = 0, col = 0;
 
    // Size of one group
    int size = (N * M) / k;
    int rem = (N * M) % k;
 
    // Element to assigned to matrix
    int start = 1, flag = 1;
 
    // Fill the matrix that have rem
    // no of parts with size size + 1
    fillMatrix(mat, row, col, size + 1,
               rem, start, M, flag);
 
    // Fill the remaining number of parts
    // with each part size is 'size'
    fillMatrix(mat, row, col, size,
               k - rem, start, M, flag);
 
    // Return the matrix
    return mat;
}
 
// Function to print the matrix
void printMatrix(int** mat, int N,
                 int M)
{
    // Traverse the rows
    for (int i = 0; i < N; ++i) {
 
        // Traverse the columns
        for (int j = 0; j < M; ++j) {
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given N, M, K
    int N = 5, M = 5, K = 6;
 
    // Function Call
    int** mat = findMatrix(N, M, K);
 
    // Function Call to print matrix
    printMatrix(mat, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int N, M;
static int [][]mat;
static int row, col, start, flag;
 
// Function to fill the matrix with
// the given conditions
static void fillMatrix(int sizeOfpart,
                       int noOfPart, 
                       int m)
{
     
    // Count of parts with size sizeOfPart
    for(int i = 0; i < noOfPart; ++i)
    {
        int count = 0;
 
        while (count < sizeOfpart)
        {
             
            // Assigning the cell
            // with no of groups
            mat[row][col] = start;
 
            // Update row
            if (col == m - 1 && flag == 1) 
            {
                row++;
                col = m;
                flag = 0;
            }
            else if (col == 0 && flag == 0)
            {
                row++;
                col = -1;
                flag = 1;
            }
 
            // Update col
            if (flag == 1)
            {
                col++;
            }
            else
            {
                col--;
            }
 
            // Increment count
            count++;
        }
 
        // For new group increment start
        start++;
    }
}
 
// Function to return the reference of
// the matrix to be filled
static void findMatrix(int k)
{
     
    // Create matrix of size N*M
    mat = new int[M][N];
 
    // Starting index of the matrix
    row = 0;
    col = 0;
 
    // Size of one group
    int size = (N * M) / k;
    int rem = (N * M) % k;
 
    // Element to assigned to matrix
    start = 1;
    flag = 1;
 
    // Fill the matrix that have rem
    // no of parts with size size + 1
    fillMatrix(size + 1, rem, M);
 
    // Fill the remaining number of parts
    // with each part size is 'size'
    fillMatrix(size, k - rem, M);
}
 
// Function to print the matrix
static void printMatrix()
{
     
    // Traverse the rows
    for(int i = 0; i < N; ++i)
    {
         
        // Traverse the columns
        for(int j = 0; j < M; ++j)
        {
            System.out.print(mat[i][j] + " ");
        }
        System.out.println();
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N, M, K
    N = 5;
    M = 5;
    int K = 6;
 
    // Function Call
    findMatrix(K);
 
    // Function Call to print matrix
    printMatrix();
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to fill the matrix with
# the given conditions
def fillMatrix( sizeOfpart,noOfPart, m):
     
    global start, flag, size, rem, row, col, mat
     
    # Count of parts with size sizeOfPart
    for i in range(noOfPart):
        count = 0;
 
        while (count < sizeOfpart):
         
            # Assigning the cell
            # with no of groups
            mat[row][col] = start;
 
            # Update row
            if (col == m - 1 and flag == 1) :
             
                row+= 1;
                col = m;
                flag = 0;
             
            elif (col == 0 and flag == 0):
             
                row+= 1;
                col = -1;
                flag = 1;
             
            # Update col
            if (flag == 1):     
                col += 1;
            else:
                col -= 1;
             
            # Increment count
            count += 1;
         
        # For new group increment start
        start += 1;
     
# Function to return the reference of
# the matrix to be filled
def findMatrix(k):
     
    global start, flag, size, rem, row, col, mat
     
    # Create matrix of size N*M
    mat = [ [0] * N for _ in range(M) ]
     
     
    # Starting index of the matrix
    row = 0;
    col = 0;
 
    # Size of one group
    size = int((N * M) / k);
    rem = (N * M) % k;
 
    # Element to assigned to matrix
    start = 1;
    flag = 1;
 
    # Fill the matrix that have rem
    # no of parts with size size + 1
    fillMatrix(size + 1, rem, M);
 
    # Fill the remaining number of parts
    # with each part size is 'size'
    fillMatrix(size, k - rem, M);
 
# Function to print matrix
def printMatrix():
     
    for row in mat:
        print(*row)
     
# Driver Code
 
# Given N, M, K
N = 5;
M = 5;
K = 6;
 
# Function Call
findMatrix(K);
 
# Function Call to prmatrix
printMatrix();
 
# This code is contributed by phasing17

C#

// C# program for the 
// above approach
using System;
class GFG{
     
static int N, M;
static int [,]mat;
static int row, col, 
           start, flag;
 
// Function to fill the 
// matrix with the given 
// conditions
static void fillMatrix(int sizeOfpart,
                       int noOfPart, 
                       int m)
{    
  // Count of parts with size 
  // sizeOfPart
  for(int i = 0; 
          i < noOfPart; ++i)
  {
    int count = 0;
 
    while (count < sizeOfpart)
    {
      // Assigning the cell
      // with no of groups
      mat[row, col] = start;
 
      // Update row
      if (col == m - 1 && 
          flag == 1) 
      {
        row++;
        col = m;
        flag = 0;
      }
      else if (col == 0 && 
               flag == 0)
      {
        row++;
        col = -1;
        flag = 1;
      }
 
      // Update col
      if (flag == 1)
      {
        col++;
      }
      else
      {
        col--;
      }
 
      // Increment count
      count++;
    }
 
    // For new group increment 
    // start
    start++;
  }
}
 
// Function to return the 
// reference of the matrix 
// to be filled
static void findMatrix(int k)
{    
  // Create matrix of 
  // size N*M
  mat = new int[M, N];
 
  // Starting index of the
  // matrix
  row = 0;
  col = 0;
 
  // Size of one group
  int size = (N * M) / k;
  int rem = (N * M) % k;
 
  // Element to assigned to 
  // matrix
  start = 1;
  flag = 1;
 
  // Fill the matrix that have
  // rem no of parts with size 
  // size + 1
  fillMatrix(size + 1, 
             rem, M);
 
  // Fill the remaining number
  // of parts with each part 
  // size is 'size'
  fillMatrix(size, k - rem, M);
}
 
// Function to print the 
// matrix
static void printMatrix()
{    
  // Traverse the rows
  for(int i = 0; i < N; ++i)
  {
    // Traverse the columns
    for(int j = 0; j < M; ++j)
    {
      Console.Write(mat[i, j] +
                    " ");
    }
    Console.WriteLine();
  }
}
 
// Driver Code
public static void Main(String[] args)
{    
  // Given N, M, K
  N = 5;
  M = 5;
  int K = 6;
 
  // Function Call
  findMatrix(K);
 
  // Function Call to 
  // print matrix
  printMatrix();
}
}
 
// This code is contributed by 29AjayKumar

Javascript

// JS program for the above approach
let N, M;
let mat;
let row, col, start, flag;
 
// Function to fill the matrix with
// the given conditions
function fillMatrix( sizeOfpart,
                        noOfPart, 
                        m)
{
     
    // Count of parts with size sizeOfPart
    for(let i = 0; i < noOfPart; ++i)
    {
        let count = 0;
 
        while (count < sizeOfpart)
        {
 
            // Assigning the cell
            // with no of groups
            mat[row][col] = start;
 
            // Update row
            if (col == m - 1 && flag == 1) 
            {
                row++;
                col = m;
                flag = 0;
            }
            else if (col == 0 && flag == 0)
            {
                row++;
                col = -1;
                flag = 1;
            }
 
            // Update col
            if (flag == 1)
            {
                col++;
            }
            else
            {
                col--;
            }
 
            // Increment count
            count++;
        }
 
        // For new group increment start
        start++;
    }
}
 
// Function to return the reference of
// the matrix to be filled
function findMatrix(k)
{
    // Create matrix of size N*M
    mat = new Array(M);
    for (var i = 0; i < M; i++)
        mat[i] = new Array(N).fill(0);
     
 
    // Starting index of the matrix
    row = 0;
    col = 0;
 
    // Size of one group
    let size = Math.floor((N * M) / k);
    let rem = (N * M) % k;
 
    // Element to assigned to matrix
    start = 1;
    flag = 1;
 
    // Fill the matrix that have rem
    // no of parts with size size + 1
    fillMatrix(size + 1, rem, M);
 
    // Fill the remaining number of parts
    // with each part size is 'size'
    fillMatrix(size, k - rem, M);
}
 
// Function to print the matrix
function printMatrix()
{
     
    // Traverse the rows
    for(let i = 0; i < N; ++i)
    {
         
        // Traverse the columns
        for(let j = 0; j < M; ++j)
        {
            process.stdout.write(mat[i][j] + " ");
        }
        console.log();
    }
}
 
// Driver Code
 
     
    // Given N, M, K
    N = 5;
    M = 5;
    let K = 6;
 
 
    // Function Call
    findMatrix(K);
 
    // Function Call to print matrix
    printMatrix();
 
 
 
// This code is contributed by phasing17

Output:

Time Complexity: O(N * M)
Auxiliary Space: O(N * M)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 neveropen!

Divide Matrix into K groups of adjacent cells having minimum difference between maximum and minimum sized groups

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Android users face nearly double the billing errors of iOS

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

EDITOR PICKS

Android users face nearly double the billing errors of iOS

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

POPULAR POSTS

Android users face nearly double the billing errors of iOS

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

POPULAR CATEGORY

ABOUT US

FOLLOW US