Find pair of rows in a binary matrix that has maximum bit difference

0 0 12 minutes read

Given a Binary Matrix. The task is to find the pair of row in the Binary matrix that has maximum bit difference Examples:

Input: mat[][] = {{1, 1, 1, 1},
                 {1, 1, 0, 1},
                 {0, 0, 0, 0}};
Output : (1, 3)
Bit difference between row numbers 1 and 3
is maximum with value 4. Bit difference 
between 1 and 2 is 1 and between 2 and 3
is 3.

Input: mat[][] = {{1 ,1 ,1 ,1 }
                  {1 ,0, 1 ,1 }
                  {0 ,1 ,0 ,0 }
                  {0, 0 ,0 ,0 }} 
Output : (2, 3)
Bit difference between rows 2 and 3 is 
maximum which is 4.

Input: mat[][] = {{1 ,0 ,1 ,1 }
                  {1 ,1 ,1 ,1 }
                  {0 ,1 ,0 ,1 }
                  {1, 0 ,0 ,0 }} 
Output : (1, 3) or (2  ,4 ) or (3 ,4 ) 
They all are having  maximum bit difference
that is 3

Simple solution of this problem is that pick each row of binary matrix one -by -one and compute maximum bit difference with rest of the rows of matrix .at last return rows those have maximum bit difference .

An Efficient solution using Trie Data Structure. Below is algorithm.

1). Create an empty Trie. Every node of Trie contains
    two children for 0 and 1 bits.
2). Insert First Row of Binary matrix into Trie 

3).Traverse rest of the rows of given Binary Matrix 
   a). For Each Row First we search maximum bit difference
       with rows that we insert before that in Trie and 
       count bit difference 
   b). For every search we update maximum bit_diff count
       if needed else not store pair of index that have
       maximum bit difference 
   c). At Last Print Pair

Implementation:

CPP

// C++ program to Find Pair of row in Binary matrix
// that has maximum Bit difference
#include<bits/stdc++.h>
using namespace std;
 
// Maximum size of matrix
const int MAX = 100;
 
struct TrieNode
{
  int leaf; //store index of visited row
  struct TrieNode *Child[2];
};
 
// Utility function to create a new Trie node
TrieNode * getNode()
{
  TrieNode * newNode = new TrieNode;
  newNode->leaf = 0;
  newNode->Child[0] = newNode->Child[1] = NULL;
  return newNode;
}
 
// utility function insert new row in trie
void insert(TrieNode *root, int Mat[][MAX], int n,
      int row_index)
{
  TrieNode * temp = root;
 
  for (int i=0; i<n; i++)
  {
    // Add a new Node into trie
    if(temp->Child[ Mat[row_index][i] ] == NULL)
      temp->Child[ Mat[row_index][i] ] = getNode();
 
    // move current node to point next node in trie
    temp = temp->Child[ Mat[row_index][i] ];
  }
 
  // store index of currently inserted row
  temp->leaf = row_index +1 ;
}
 
// utility function calculate maximum bit difference of
// current row with previous visited row of binary matrix
pair<int, int> maxBitDiffCount(TrieNode * root,
        int Mat[][MAX], int n, int row_index)
{
  TrieNode * temp = root;
  int count = 0;
 
  // Find previous visited row of binary matrix
  // that has starting bit same as current row
  for (int i= 0 ; i < n ; i++)
  {
    // First look for same bit in trie
    if (temp->Child[ Mat[row_index][i] ] != NULL)
      temp = temp->Child[ Mat[row_index][i] ];
 
    // Else looking for opposite bit
    else if (temp->Child[1 - Mat[row_index][i]] != NULL)
    {
      temp = temp->Child[1- Mat[row_index][i]];
      count++;
    }
  }
 
  int leaf_index = temp->leaf;
  int count1 = 0 ;
  temp = root;
 
  // Find previous visited row of binary matrix
  // that has starting bit opposite to current row
  for (int i= 0 ; i < n ; i++)
  {
    // First looking for opposite bit
    if (temp->Child[ 1 - Mat[row_index][i] ] !=NULL)
    {
      temp = temp->Child[ 1- Mat[row_index][i] ];
      count1++;
    }
 
    // Else look for same bit in trie
    else if (temp->Child[ Mat[row_index][i] ] != NULL)
      temp = temp->Child[ Mat[row_index][i] ];
  }
 
  pair <int ,int> P = count1 > count ?
            make_pair(count1, temp->leaf):
            make_pair(count, leaf_index);
 
  // return pair that contain both bit difference
  // count and index of row with we get bit
  // difference
  return P;
}
 
// Returns maximum bit difference pair of row
void maxDiff( int mat[][MAX], int n, int m)
{
  TrieNode * root = getNode();
 
  // Insert first matrix row in trie
  insert(root, mat, m, 0);
 
  int max_bit_diff = INT_MIN;
  pair <int ,int> P, temp ;
 
  // Traverse all rest row of binary matrix
  for (int i = 1 ; i < n; i++)
  {
    // compute bit difference with previous visited
    // rows of matrix
    temp = maxBitDiffCount(root, mat, m ,i);
 
    // update maximum bit difference
    if (max_bit_diff < temp.first )
    {
      max_bit_diff = temp.first;
      P = make_pair( temp.second, i+1);
    }
 
    // insert current row value into Trie
    insert(root, mat, m, i );
  }
 
  // print maximum bit difference pair in row
  cout << "(" << P.first <<", "<< P.second << ")";
}
 
// Driver program
int main()
{
  int mat[][MAX] = {{0 ,1 ,0 ,1, 0 },
    {1, 0, 1 ,1 ,0 },
    {0 ,0 ,1 ,0, 1 }
  };
  maxDiff(mat, 3, 5) ;
  return 0;
}

Java

// Importing required library
import java.util.*;
class Pair
{
    int first,second;
    Pair(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
}
public class Main {
    // Maximum size of matrix
    static final int MAX = 100;
 
    static class TrieNode {
        int leaf; // store index of visited row
        TrieNode[] Child = new TrieNode[2];
 
        // Constructor
        TrieNode() {
            this.leaf = 0;
            this.Child[0] = null;
            this.Child[1] = null;
        }
    }
 
    // Utility function to create a new Trie node
    static TrieNode getNode() {
        TrieNode newNode = new TrieNode();
        return newNode;
    }
 
    // utility function insert new row in trie
    static void insert(TrieNode root, int[][] Mat, int n, int row_index) {
        TrieNode temp = root;
 
        for (int i = 0; i < n; i++) {
            // Add a new Node into trie
            if (temp.Child[(Mat[row_index][i])] == null)
                temp.Child[(Mat[row_index][i])] = getNode();
 
            // move current node to point next node in trie
            temp = temp.Child[(Mat[row_index][i])];
        }
 
        // store index of currently inserted row
        temp.leaf = row_index + 1;
    }
 
    // utility function calculate maximum bit difference of
    // current row with previous visited row of binary matrix
    static Pair maxBitDiffCount(TrieNode root, int[][] Mat, int n, int row_index) {
        TrieNode temp = root;
        int count = 0;
 
        // Find previous visited row of binary matrix
        // that has starting bit same as current row
        for (int i = 0; i < n; i++) {
            // First look for same bit in trie
            if (temp.Child[(Mat[row_index][i])] != null)
                temp = temp.Child[(Mat[row_index][i])];
 
                // Else looking for opposite bit
            else if (temp.Child[1 - Mat[row_index][i]] != null) {
                temp = temp.Child[1 - Mat[row_index][i]];
                count++;
            }
        }
 
        int leaf_index = temp.leaf;
        int count1 = 0;
        temp = root;
 
        // Find previous visited row of binary matrix
        // that has starting bit opposite to current row
        for (int i = 0; i < n; i++) {
            // First looking for opposite bit
            if (temp.Child[1 - Mat[row_index][i]] != null) {
                temp = temp.Child[1 - Mat[row_index][i]];
                count1++;
            }
 
            // Else look for same bit in trie
            else if (temp.Child[(Mat[row_index][i])] != null)
                temp = temp.Child[(Mat[row_index][i])];
        }
 
        Pair P = count1 > count ?
                new Pair(count1, temp.leaf) :
                new Pair(count, leaf_index);
 
        // return pair that contain both bit difference
        // count and index of row with we get bit
        // difference
        return P;
    }
 
    // Returns maximum bit difference pair of row
    static void maxDiff(int[][] mat, int n, int m) {
        TrieNode root = getNode();
 
        // Insert first matrix row in trie
        insert(root, mat, m, 0);
 
        int max_bit_diff = Integer.MIN_VALUE;
        Pair P=null;Pair temp=null;
 
        // Traverse all rest row of binary matrix
        for (int i = 1; i < n; i++) {
            // compute bit difference with previous visited
            // rows of matrix
            temp = maxBitDiffCount(root, mat, m, i);
 
            // update maximum bit difference
            if (max_bit_diff < temp.first) {
                max_bit_diff = temp.first;
                P = new Pair(temp.second, i + 1);
            }
 
            // insert current row value into Trie
            insert(root, mat, m, i);
        }
        System.out.println("("+P.first+", "+P.second+")");
    }
 
    public static void main(String[] args) {
        int mat[][] = {{0 ,1 ,0 ,1, 0 },
            {1, 0, 1 ,1 ,0 },
            {0 ,0 ,1 ,0, 1 }
        };
        maxDiff(mat, 3, 5) ;
    }
}

Python3

import sys
 
# Maximum size of matrix
MAX = 100
 
class TrieNode:
    def __init__(self):
        self.leaf = 0  # store index of visited row
        self.Child = [None] * 2
 
# Utility function to create a new Trie node
def getNode():
    newNode = TrieNode()
    newNode.leaf = 0
    newNode.Child = [None] * 2
    return newNode
 
# utility function insert new row in trie
def insert(root, Mat, n, row_index):
    temp = root
 
    for i in range(n):
        # Add a new Node into trie
        if temp.Child[(Mat[row_index][i])] == None:
            temp.Child[(Mat[row_index][i])] = getNode()
 
        # move current node to point next node in trie
        temp = temp.Child[(Mat[row_index][i])]
 
    # store index of currently inserted row
    temp.leaf = row_index + 1
 
# utility function calculate maximum bit difference of
# current row with previous visited row of binary matrix
def maxBitDiffCount(root, Mat, n, row_index):
    temp = root
    count = 0
 
    # Find previous visited row of binary matrix
    # that has starting bit same as current row
    for i in range(n):
        # First look for same bit in trie
        if temp.Child[(Mat[row_index][i])] != None:
            temp = temp.Child[(Mat[row_index][i])]
 
        # Else looking for opposite bit
        elif temp.Child[1 - Mat[row_index][i]] != None:
            temp = temp.Child[1 - Mat[row_index][i]]
            count += 1
 
    leaf_index = temp.leaf
    count1 = 0
    temp = root
 
    # Find previous visited row of binary matrix
    # that has starting bit opposite to current row
    for i in range(n):
        # First looking for opposite bit
        if temp.Child[1 - Mat[row_index][i]] != None:
            temp = temp.Child[1 - Mat[row_index][i]]
            count1 += 1
 
        # Else look for same bit in trie
        elif temp.Child[(Mat[row_index][i])] != None:
            temp = temp.Child[(Mat[row_index][i])]
 
    P = (count1, temp.leaf) if count1 > count else (count, leaf_index)
 
    # return pair that contain both bit difference
    # count and index of row with we get bit
    # difference
    return P
 
# Returns maximum bit difference pair of row
def maxDiff(mat, n, m):
    root = getNode()
 
    # Insert first matrix row in trie
    insert(root, mat, m, 0)
 
    max_bit_diff = -sys.maxsize
    P, temp = None, None
 
    # Traverse all rest row of binary matrix
    for i in range(1, n):
        # compute bit difference with previous visited
        # rows of matrix
        temp = maxBitDiffCount(root, mat, m, i)
 
        # update maximum bit difference
        if max_bit_diff < temp[0]:
            max_bit_diff = temp[0]
            P = (temp[1], i+1)
 
        # insert current row value into Trie
        insert(root, mat, m, i)
 
    # print maximum bit difference pair in row
    print(f"({P[0]}, {P[1]})")
 
# Driver program
if __name__ == "__main__":
    mat = [[0, 1, 0 ,1, 0 ],
    [1, 0, 1 ,1 ,0 ],
    [0 ,0 ,1 ,0, 1 ]
    ]
    maxDiff(mat, 3, 5)
 
# This code is contributed by Prince Kumar

C#

// C# program to Find Pair of row in Binary matrix
// that has maximum Bit difference
using System;
 
public class TrieNode
{
  public int Leaf;//store index of visited row
  public TrieNode[] Child;
 
  public TrieNode()
  {
    Leaf = 0;
    Child = new TrieNode[2];
    Child[0] = Child[1] = null;
  }
}
 
public class MaxBitDifference
{
  // Maximum size of matrix
  private const int MAX = 100;
  // Utility function to create a new Trie node
  private static TrieNode GetNode()
  {
    return new TrieNode();
  }
 
  // utility function insert new row in trie
  private static void Insert(TrieNode root, int[,] mat, int n, int rowIndex)
  {
    var temp = root;
 
    for (var i = 0; i < n; i++)
    {
 
      // Add a new Node into trie
      if (temp.Child[(mat[rowIndex, i])] == null)
      {
        temp.Child[(mat[rowIndex, i])] = GetNode();
      }
 
      // move current node to point next node in trie
      temp = temp.Child[(mat[rowIndex, i])];
    }
 
    // store index of currently inserted row
    temp.Leaf = rowIndex + 1;
  }
 
  // utility function calculate maximum bit difference of
  // current row with previous visited row of binary matrix
  private static Tuple<int, int> MaxBitDiffCount(TrieNode root, int[,] mat, int n, int rowIndex)
  {
    var temp = root;
    var count = 0;
 
    // Find previous visited row of binary matrix
    // that has starting bit same as current row
    for (var i = 0; i < n; i++)
    {
 
      // First look for same bit in trie
      if (temp.Child[(mat[rowIndex, i])] != null)
      {
        temp = temp.Child[(mat[rowIndex, i])];
      }
 
      // Else looking for opposite bit
      else if (temp.Child[1 - mat[rowIndex, i]] != null)
      {
        temp = temp.Child[1 - mat[rowIndex, i]];
        count++;
      }
    }
 
    var leafIndex = temp.Leaf;
    var count1 = 0;
    temp = root;
 
    // Find previous visited row of binary matrix
    // that has starting bit opposite to current row
    for (var i = 0; i < n; i++)
    {
 
      // First looking for opposite bit
      if (temp.Child[1 - mat[rowIndex, i]] != null)
      {
        temp = temp.Child[1 - mat[rowIndex, i]];
        count1++;
      }
 
      // Else look for same bit in trie
      else if (temp.Child[(mat[rowIndex, i])] != null)
      {
        temp = temp.Child[(mat[rowIndex, i])];
      }
    }
 
    var P = count1 > count ? new Tuple<int, int>(count1, temp.Leaf) : new Tuple<int, int>(count, leafIndex);
 
    // return pair that contain both bit difference
    // count and index of row with we get bit
    // difference
    return P;
  }
 
  // Returns maximum bit difference pair of row
  public static void MaxDiff(int[,] mat, int n, int m)
  {
    var root = GetNode();
 
    // Insert first matrix row in trie
    Insert(root, mat, m, 0);
 
    var maxBitDiff = int.MinValue;
    Tuple<int, int> P = null, temp = null;
 
    // Traverse all rest row of binary matrix
    for (var i = 1; i < n; i++)
    {
 
      // compute bit difference with previous visited
      // rows of matrix
      temp = MaxBitDiffCount(root, mat, m, i);
 
      // update maximum bit difference
      if (maxBitDiff < temp.Item1)
      {
        maxBitDiff = temp.Item1;
        P = new Tuple<int, int>(temp.Item2, i + 1);
      }
 
      // insert current row value into Trie
      Insert(root, mat, m, i);
    }
 
    // print maximum bit difference pair in row
    Console.WriteLine("({0}, {1})", P.Item1, P.Item2);
  }
 
  // Driver program
  public static void Main()
  {
    var mat = new int[3, 5] {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 0}, {0, 0, 1, 0, 1}};
    MaxDiff(mat, 3, 5);
  }
}

Javascript

// Maximum size of matrix
const MAX = 100;
 
class TrieNode {
  constructor() {
    this.leaf = 0; // store index of visited row
    this.Child = [null, null];
  }
}
 
// Utility function to create a new Trie node
function getNode() {
  const newNode = new TrieNode();
  newNode.leaf = 0;
  newNode.Child = [null, null];
  return newNode;
}
 
// utility function insert new row in trie
function insert(root, Mat, n, row_index) {
  let temp = root;
 
  for (let i = 0; i < n; i++) {
    // Add a new Node into trie
    if (temp.Child[(Mat[row_index][i])] == null) {
      temp.Child[(Mat[row_index][i])] = getNode();
    }
 
    // move current node to point next node in trie
    temp = temp.Child[(Mat[row_index][i])];
  }
 
  // store index of currently inserted row
  temp.leaf = row_index + 1;
}
 
// utility function calculate maximum bit difference of
// current row with previous visited row of binary matrix
function maxBitDiffCount(root, Mat, n, row_index) {
  let temp = root;
  let count = 0;
 
  // Find previous visited row of binary matrix
  // that has starting bit same as current row
  for (let i = 0; i < n; i++) {
    // First look for same bit in trie
    if (temp.Child[(Mat[row_index][i])] != null) {
      temp = temp.Child[(Mat[row_index][i])];
    }
 
    // Else looking for opposite bit
    else if (temp.Child[1 - Mat[row_index][i]] != null) {
      temp = temp.Child[1 - Mat[row_index][i]];
      count += 1;
    }
  }
 
  let leaf_index = temp.leaf;
  let count1 = 0;
  temp = root;
 
  // Find previous visited row of binary matrix
  // that has starting bit opposite to current row
  for (let i = 0; i < n; i++) {
    // First looking for opposite bit
    if (temp.Child[1 - Mat[row_index][i]] != null) {
      temp = temp.Child[1 - Mat[row_index][i]];
      count1 += 1;
    }
 
    // Else look for same bit in trie
    else if (temp.Child[(Mat[row_index][i])] != null) {
      temp = temp.Child[(Mat[row_index][i])];
    }
  }
 
  let P = count1 > count ? [count1, temp.leaf] : [count, leaf_index];
 
  // return pair that contain both bit difference
  // count and index of row with we get bit
  // difference
  return P;
}
 
// Returns maximum bit difference pair of row
function maxDiff(mat, n, m) {
  const root = getNode();
 
  // Insert first matrix row in trie
  insert(root, mat, m, 0);
 
  let max_bit_diff = -Infinity;
  let P = null;
  let temp = null;
 
  // Traverse all rest row of binary matrix
  for (let i = 1; i < n; i++) {
    // compute bit difference with previous visited
    // rows of matrix
    temp = maxBitDiffCount(root, mat, m, i);
 
    // update maximum bit difference
    if (max_bit_diff < temp[0]) {
      max_bit_diff = temp[0];
      P = [temp[1], i + 1];
    }
 
    // insert current row value into Trie
    insert(root, mat, m, i);
  }
 
  // print maximum bit difference pair in row
  console.log(`(${P[0]}, ${P[1]})`);
}
 
// Driver program
const mat = [
  [0, 1, 0, 1, 0],
  [1, 0, 1, 1, 0],
  [0, 0, 1, 0, 1]
];
maxDiff(mat, 3, 5);

Output

(1, 3)

Time Complexity:O(n)
Auxiliary Space: O(n)

If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

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