Minimize count of adjacent row swaps to convert given Matrix to a Lower Triangular Matrix | C ++ program to implement the above approach ; Function to count the minimum number of adjacent swaps ; Stores the size of the given matrix ; Stores the count of zero at the end of each row ; Traverse the given matrix ; Count of 0 s at the end of the ith row ; Stores the count of swaps ; Traverse the cntZero array ; If count of zero in the i - th row < ( N - i - 1 ) ; Stores the index of the row where count of zero > ( N - i - 1 ) ; If no row found that satisfy the condition ; Swap the adjacent row ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minAdjSwaps ( vector < vector < int > > & mat ) { int N = mat . size ( ) ; vector < int > cntZero ( N , 0 ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = N - 1 ; j >= 0 && mat [ i ] [ j ] == 0 ; j -- ) { cntZero [ i ] ++ ; } } int cntSwaps = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( cntZero [ i ] < ( N - i - 1 ) ) { int First = i ; while ( First < N && cntZero [ First ] < ( N - i - 1 ) ) { First ++ ; } if ( First == N ) { return -1 ; } while ( First > i ) { swap ( cntZero [ First ] , cntZero [ First - 1 ] ) ; First -- ; cntSwaps ++ ; } } } return cntSwaps ; } int main ( ) { vector < vector < int > > mat = { { 0 , 0 , 2 } , { 3 , 1 , 0 } , { 4 , 0 , 0 } } ; cout << minAdjSwaps ( mat ) ; }