Finding largest rectangle in a given matrix when swapping of columns is possible

you are given a matrix with 0 and 1's. you have to find the largest rectangle in the matrix such that you can swap columns
with any other column.
Ex-  0 1 0 1 0
     0 1 0 1 1
     1 1 0 1 0
the largest rectangle's area is 6 in this case because we can swap column 2 with column 3 so
the matrix after swapping will be
     0 0 1 1 0
     0 0 1 1 1
     1 0 1 1 0

Solution - 

  step 1 - first of all we have to calculate no of consecutive 1's in any particular column so we will take a 2D array
to store them
so for this the values in array will be
    0 1 0 1 0
    0 2 0 2 1
    1 3 0 3 0
so the mechanism of filling the array will
  ar[i][j] = ar[i-1][j]+1   if i>0 && a[i][j]==1
           = 1              if i==0 && a[i][j]=1
           = 0              else

step 2 - we will sort the rows in decreasing fashion
 so after sorting step the matrix will be
    1 1 0 0 0
    2 2 1 0 0
    3 3 1 0 0

step 3 - now we will traverse each row and check for the max area

#include<bits/stdc++.h>
using namespace std;

int n;

int rect(int a[][100]){

int i,j;

int ar[n+1][n+1];

//constructing the histogram

for(i=0;i<n;i++){

ar[0][i]=a[0][i];  // if we are in the first row

for(j=1;j<n;j++){

if(a[j][i]==0){

ar[j][i]=0;

}else{

ar[j][i]=ar[j-1][i]+1;

}

}

}

int k;

//sorting rows

//using count sort for better time complexity

for(i=0;i<n;i++){

int br[n+1]={0},x=0;

for(j=0;j<n;j++){

br[ar[i][j]]++;   // counting occurrence

}

for(j=n;j>=0;j--){

if(br[j]>0){

for(k=0;k<br[j];k++){

ar[i][x]=j;

x++;

}

}

}

}

//checking for the maximum value

int x;

int max=0;

for(i=0;i<n;i++){

for(j=0;j<n;j++){

x=(j+1)*ar[i][j];

if(x>max){

max=x;

}

}

}

return max;

}

int main(){

int b,c,d,i,j,a[100][100];

scanf("%d",&n);

for(i=0;i<n;i++){

for(j=0;j<n;j++){

scanf("%d",&a[i][j]);

}

}

printf("area of the biggest rectangle is = %d\n",rect(a));

return 0;

}

   

Time complexity = O(n^2) if we use count sort for sorting rows otherwise it will be O(n^2*log(n)).
Extra space = O(n^2)

Minimum number of jumps to reach end

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Example:

Input: arr[] = {1, 2, 5, 7, 6, 2, 6, 3, 2, 8, 9}
Output: 3 (1-> 2 -> 7 ->9)

First element is 1, so can only go to 2. Second element is 2, so can make at most 2 steps eg to 5 or 7.

Solution - we can do it with several methods.

              (1) recursion         (2) DP

here i'll only discuss the dynamic programming approach

(1) Time - O(n^2)  & Space - O(n)

       In this method, we will maintain an array from left to right such that the array contains information about  minimum number of jumps needed to reach ar[i] from ar[0]. So the nth element of the new array will have the information about minimum number of steps to reach the end.

#include<bits/stdc++.h>                                                                                                 using namespace std;

// Returns minimum number of jumps to reach nth step from the first

int minjumps(int ar[], int n){

    int jump[n+2];  // jump[n-1] will hold the result

    if (n == 0 || ar[0] == 0) //impossible situation

        return INT_MAX;

    int i,j;

    for(i=0;i<n;i++)

    jump[i]=INT_MAX;

    jump[0] = 0; //no of step to reach the first step

    // Find the minimum number of jumps to reach arr[i]

    // from arr[0], and assign this value to jumps[i]

    for (i = 0; i < n; i++){

        for (j = 1; j <= ar[i] && i+j<n; j++){

            jump[i+j]=min(jump[i+j],jump[i]+1);

        }

    }

    return jump[n-1];

}

int main()

{

    int ar[100000],n,i,j;

    scanf("%d",&n);

    for(i = 0; i < n; i++){

        scanf("%d",&ar[i]);

    }

    printf("Minimum number of jumps to reach end is %d ", minjumps(ar,n));

    return 0;

}

(2) Time - O(n) & Space - O(n) - 

basically i used the information that if we updated an index once then we don't need to update that for further numbers, because whatever we'll try we can't get less steps then that.

#include<bits/stdc++.h>                                                                                              using namespace std;

// Returns minimum number of jumps to reach nth step from first

int minjumps(int ar[], int n){

    int jump[n+2];  // jump[n-1] will hold the result

    if (n == 0 || ar[0] == 0) //impossible situation

        return INT_MAX;

       int i,j;

    jump[0] = 0; //no of step to reach the first step

    // from arr[0], and assign this value to jumps[i]

    int k=0; //this will avoid repeat for (i = 0; i < n; i++){ for (j = k+1; j <= i+ar[i] && j<n; j++) { jump[j]=jump[i]+1; } k=max(k,i+ar[i]); }

    return jump[n-1];

}

int main()

{

    int ar[100000],n,i,j;

    scanf("%d",&n);

    for(i = 0; i < n; i++){

        scanf("%d",&ar[i]);

    }

    printf("Minimum number of jumps to reach end is %d ", minjumps(ar,n));

    return 0;

}