Table of Contents
Matrix Land – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Matrix Land HackerRank Solution
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#define rep(i,j,k) for(register int i = j; i <= k; ++i)
#define dow(i,j,k) for(register int i = j; i >= k; --i)
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
inline int read() {
int s = 0, t = 1; char c = getchar();
while( !isdigit(c) ) { if( c == '-' ) t = -1; c = getchar(); }
while( isdigit(c) ) s = s * 10 + c - 48, c = getchar();
return s * t;
}
const int N = 4e6+5, inf = 1e9+7;
int n, m, maxl, now, pre, f[2][N], v[N], g[N], h[N], sum[N];
int main() {
n = read(), m = read(), now = 0, pre = 1;
rep(i,1,n) {
swap(now,pre);
rep(j,1,m) v[j] = read();
rep(j,1,m) sum[j] = sum[j-1] + v[j];
rep(j,1,m) g[j] = max(g[j-1]+v[j],0);
dow(j,m,1) h[j] = max(h[j+1]+v[j],0);
maxl = -inf;
rep(j,1,m) {
maxl = max(maxl,f[pre][j]-sum[j-1]+g[j-1]);
f[now][j] = maxl+sum[j]+h[j+1];
}
maxl = -inf;
dow(j,m,1) {
maxl = max(maxl,f[pre][j]+sum[j]+h[j+1]);
f[now][j] = max(f[now][j],maxl-sum[j-1]+g[j-1]);
}
}
int ans = 0;
rep(i,1,m) ans = max(ans,f[now][i]);
cout<<ans<<endl;
return 0;
}
Java Matrix Land HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] a = new int[m];
long[] left = new long[m];
long[] right = new long[m];
long[] prev = new long[m];
long[] current = new long[m];
long[] leftplus = new long[m];
long[] rightplus = new long[m];
for(int A_i = 0; A_i < n; A_i++){
for(int A_j = 0; A_j < m; A_j++){
a[A_j] = in.nextInt();
}
for (int i = 1; i < m; i++)
{
left[i] = Math.max(left[i - 1] + a[i - 1], 0);
}
for (int i = m - 2; i >= 0; i--)
{
right[i] = Math.max(right[i + 1] + a[i + 1], 0);
}
leftplus[0] = prev[0] + a[0];
for (int i = 1; i < m; i++)
{
leftplus[i] = Math.max(prev[i] + a[i] + left[i], leftplus[i - 1] + a[i]);
}
rightplus[m - 1] = prev[m - 1] + a[m - 1];
for (int i = m - 2; i >= 0; i--)
{
rightplus[i] = Math.max(prev[i] + a[i] + right[i], rightplus[i + 1] + a[i]);
}
for (int i = 0; i < m; i++)
{
current[i] = Math.max(leftplus[i] + right[i], rightplus[i] + left[i]);
}
long[] temp = current;
current = prev;
prev = temp;
}
long result = Long.MIN_VALUE;
for (int i = 0; i < m; i++)
{
result = Math.max(prev[i], result);
}
System.out.println(result);
in.close();
}
}
Python 3 Matrix Land HackerRank Solution
import os, sys
with open('progIn.txt', 'w') as file:
for line in sys.stdin:
file.write(line)
prog = r"""
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <utility>
using namespace std;
int main() {
int m, n;
scanf("%d %d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
for ( int i = 0; i < n; ++i ) for ( int j = 0; j < m; ++j ) scanf("%d", &a[i][j]);
vector<long> foundation (m);
for ( int i = n - 1; i > -1; --i ) {
vector<int> build = a[i];
multiset<long> forwards, backwards;
vector<int> pf(m), pb(m), l(m), r(m);
pf[0] = build[0]; pb[m-1] = build[m-1];
for ( int j = 1; j < m; ++j ) {
pf[j] = build[j] + pf[j-1];
}
for ( int j = m - 2; j > -1; --j ) {
pb[j] = build[j] + pb[j+1];
}
r[m-1] = m - 1;
for ( int j = m - 2; j > -1; --j ) {
if ( pf[r[j+1]] <= pf[j] ) {
r[j] = j;
} else {
r[j] = r[j+1];
}
}
l[0] = 0;
for ( int j = 1; j < m; ++j ) {
if ( pb[l[j-1]] <= pb[j] ) {
l[j] = j;
} else {
l[j] = l[j-1];
}
}
vector<long> foundation2(m);
int offsetf = 0, offsetb = 0;
//when we fill these guys up, we need to add: prefix, foundation, AND RIGHT BOUND.
for ( int j = 0; j < m; ++j ) {
long val = pf[j] + foundation[j];
if ( j < m - 1 ) {
val += pf[r[j]] - pf[j];
// cout << "ROW " << i << " COL " << j << ": ADDED " << pf[r[j]] - pf[j] << ", since r[j] = " << r[j]
// << " and pf[r[j]] = " << pf[r[j]] << " and pf[j] = " << pf[j] << endl;
}
// cout << "ROW " << i << " COL " << j << ": " << "Inserting (FB) = " << val << endl;
forwards.insert(val);
}
backwards.insert(pb[0] + foundation[0]);
foundation2[0] = *(forwards.rbegin());
//cout << "pf: ";
//for ( auto u : pf ) cout << u << ' ';
//cout << endl;
//cout << "LJ: ";
//for ( auto u : l ) cout << u << ' ';
//cout << endl;
for ( int j = 1; j < m; ++j ) {
//cout << "-----------" << endl;
offsetf = -pf[j-1];
long erasable = pf[j-1] + foundation[j-1] + pf[r[j-1]] - pf[j-1];
// cout << "ALSO SIZE IS " << forwards.size() << "; and just erased one!" << endl;
forwards.erase(forwards.find(erasable));
long val = pb[j] + foundation[j];
int left_bonus = j == l[j]
? (0)
: l[j] == 0
? pf[j-1]
: pf[j-1] - pf[l[j-1]-1];
val += left_bonus;
backwards.insert(val);
offsetb = j >= m - 1? 0 : -pb[j+1];
/*if ( j != l[j] && l[j] != 0 ) {
left_bonus = pf[j-1] - pf[l[j-1]];
} else {
cout << "keep debugging " << endl;
}*/
//cout << "left_bonus: " << left_bonus << endl;
int right_bonus = pf[r[j]] - pf[j];
// cout << "i: " << i << "; j: " << j << ";frb: " << *(forwards.rbegin()) << ";brb: " << *(backwards.rbegin()) << endl;
// cout<< "of: "<<offsetf<< "; ob: " << offsetb << endl;
// cout << "lb: " << left_bonus << "; rb: " << right_bonus << endl;
// cout << "lj: " << l[j] << "; rj: " << r[j] << endl;
foundation2[j] = forwards.size()
? max( *(forwards.rbegin()) + offsetf + left_bonus, *(backwards.rbegin()) + offsetb + right_bonus)
: left_bonus + *(backwards.rbegin()) + offsetb;
// cout << "computed value: " << foundation2[j] << endl;
}
// for ( auto u : foundation ) cout << u << ' ';
// cout << endl;
foundation = foundation2;
}
// for ( auto u : foundation ) cout << u << ' ';
// cout << endl;
long b = -2000000000;
for ( auto i : foundation ) b = max(b, i);
cout << b << endl;
}"""
if not os.path.isfile('compiled.txt'):
open('prog.cpp', 'w').write(prog)
os.system("g++ -std=c++17 -O3 -oprog prog.cpp")
open('compiled.txt', 'w').write('BRAH')
os.system("./prog < progIn.txt > progOut.txt")
print(open('progOut.txt', 'r').read().strip())
C Matrix Land HackerRank Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int verbose = 0;
void fill_left_right(int *left, int *right, int cols, int *A){
int i,v;
left[0] = A[0];
for(i=1;i<cols;i++)
if(left[i-1]>0)
left[i] = A[i] + left[i-1];
else
left[i] = A[i];
right[cols-1] = A[cols-1];
for(i=cols-2;i>=0;i--)
if(right[i+1]>0)
right[i] = A[i] + right[i+1];
else
right[i] = A[i];
}
void fill_max_left_right(int *base,int *maxL, int *maxR, int cols, int *A, int *left, int *right){
int i,u,v;
maxL[0] = A[0] + base[0];
for(i=1;i<cols;i++){
u = A[i] + maxL[i-1];
v = left[i] + base[i];
maxL[i] = u > v ? u : v;
}
maxR[cols-1] = A[cols-1] + base[cols-1];
for(i=cols-2;i>=0;i--){
u = A[i] + maxR[i+1];
v = right[i] + base[i];
maxR[i] = u > v ? u : v;
}
if(verbose){
printf("maxL:");
for(i=0;i<cols;i++)
printf(" %d",maxL[i]);
printf("\nmaxR:");
for(i=0;i<cols;i++)
printf(" %d",maxR[i]);
printf("\n");
}
for(i=0;i<cols;i++){
u = maxL[i] + right[i] - A[i];
v = maxR[i] + left[i] - A[i];
base[i] = u > v ? u : v;
}
}
int matrixLand(int rows, int cols, int** A) {
// Complete this function
int r,c;
int best,i;
int *left,*right,*base;
int *maxL,*maxR;
base = (int *) malloc(cols * sizeof(int));
left = (int *) malloc(cols * sizeof(int));
right = (int *) malloc(cols * sizeof(int));
maxL = (int *) malloc(cols * sizeof(int));
maxR = (int *) malloc(cols * sizeof(int));
fill_left_right(left, right, cols, A[rows-1]);
for(i=0;i<cols;i++)
base[i] = left[i] + right[i] - A[rows-1][i];
//fill_left_right(maxL, maxR, cols, A[rows-1]);
//for(i=0;i<cols;i++)
// base[i] = maxL[i] > maxR[i] ? maxL[i] : maxR[i];
//for(i=0;i<cols;i++)
// base[i] = 0;
for(r=rows-2;r>=0;r--){
fill_left_right(left, right, cols, A[r]);
if(verbose){
printf("left %02d:",r);
for(c=0;c<cols;c++)
printf(" %d",left[c]);
printf("\nright%02d:",r);
for(c=0;c<cols;c++)
printf(" %d",right[c]);
printf("\n");
}
fill_max_left_right(base,maxL,maxR,cols,A[r],left,right);
if(verbose){
printf("base %02d:",r);
for(c=0;c<cols;c++)
printf(" %d",base[c]);
printf("\n");
}
}
best = base[0];
for(i=1;i<cols;i++)
if(base[i]>best)
best = base[i];
free(base);
free(maxL); free(maxR);
free(left); free(right);
return best;
}
int main() {
int n;
int m;
int **A,i,j;
verbose = 0;
scanf("%i %i", &n, &m);
A = (int **) malloc(n * sizeof(int *));
for(i=0;i<n;i++)
A[i] = (int *) malloc(m * sizeof(int));
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
scanf("%i",&A[i][j]);
}
}
if(verbose){
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%d ",A[i][j]);
}
printf("\n");
}
}
int result = matrixLand(n, m, A);
printf("%d\n", result);
for(i=0;i<n;i++)
free(A[i]);
free(A);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
